[Math] Draw a graph with 8 vertices, all of odd degree, that doesn’t contain a path of length 3, or explain why such a graph doesn’t exist.

combinatoricsgraph theory

Problem: Draw a graph with $8$ vertices, all of odd degree, that doesn't contain a path of length $3$, or explain why such a graph doesn't exist.

My approach

  1. What is a path of length $3$? $\implies$ Path $3$ means that there are $3$ edges $(i,j)$, $(j,k)$, $(k,l)$ that connect $j$ and $l$ (Thanks Patrick)
  2. How do we prove a graph problem??? induction? inversion?

Best Answer

Take a graph with $8$ vertices, with one central vertex $v$ of degree $7$, and no edges other than the edges from $v$.

Then every vertex other than $v$ has degree $1$.

It's easy to see that there are no paths of length $3$.

Thus, such a graph does exist.

For another example, since disconnected graphs are not explicitly disallowed, consider a graph with $8$ vertices, and $4$ pairwise disjoint edges. Then every vertex has degree $1$, and there are no paths of length greater than $1$.

Related Question