# Graph Theory: How do we know Hamiltonian Path exists in graph where every vertex has degree ≥3?

I am trying to prove that if every node of a graph G has degree of at least 3 then G contains a cycle and a chord. My current approach is as follows:

1. Separate the graph G into connected components and consider any component C.
2. There exists a (hamiltonian) path that includes all the vertices in C. Label these vertices $V_0$...$V_k$.
3. Consider $V_0$. In addition to being connected to $V_1$, it must also be connected with two other vertices on the path, $V_i$ and $V_j$, where $i < j$.
4. We therefore have a cycle $\{V_0,V_1,V_2,...,V_i,...,V_j,V_0\}$. We also have a chord (a connection between two points within a cycle) between $V_i$ and $V_0$. Thus G contains both a cycle and a chord.

The part that I bolded and italicized is the part that's giving me trouble. I don't see how I can know that there is necessarily a path that connects all the vertices in C. And if such a path does not exist then I'm not sure how to get this proof to work.

EDIT

I thought of a possible solution but I want to confirm that it is valid:

1. Separate the graph G into connected components and consider any component C.
2. Consider a path of maximum length within C. Label these vertices $V_0$...$V_k$.
3. We know that $V_0$ and $V_k$ cannot connect to vertices outside of the current path, because otherwise the current path would not be a maximal path. Thus $V_0$ and $V_k$ must only be connected to vertices along the path.
4. Consider $V_0$. In addition to being connected to $V_1$, it must also be connected with two other vertices on the path, $V_i$ and $V_j$, where $i < j$.
5. We therefore have a cycle $\{V_0,V_1,V_2,...,V_i,...,V_j,V_0\}$. We also have a chord (a connection between two points within a cycle) between $V_i$ and $V_0$. Thus G contains both a cycle and a chord.
• It's simply not true that such a graph must have a Hamiltonian path. See Euler's Königsberg problem, for instance. – TonyK Nov 13 '13 at 8:50
• @TonyK maybe I didn't get your example right, but if you mean the Konigsberg graph, then it definitely has a Hamiltonian path (even a Hamiltonian cycle). – DKal Nov 13 '13 at 9:01
• @TonyK The Königsberg graph has no Eulerian path, but it does have a Hamiltonian path, in fact it has a Hamiltonian cycle. – bof Nov 13 '13 at 9:01
• according to your edit it seems that it is enough for you to have a cycle with a chord in $G$ (not necessarily a cycle that contains ALL vertices in some connected component of $G$). – DKal Nov 13 '13 at 9:06
• The proof in your edit is fine, so you don't need that false proposition about a Hamiltonian path. – bof Nov 13 '13 at 9:21

Here's an example of a connected $3$-regular graph with no Hamiltonian path. Let $H_1,H_2,H_3$ be three vertex-disjoint copies of $K_4$. For each $i\in\{1,2,3\}$ choose an edge $e_i$ of $H_i$ and subdivide it, making the midpoint of $e_i$ into a new vertex $x_i$. Finally, take a new vertex $y$ and add edges $x_1y,x_2y,x_3y$. This connected $3$-regular graph on $16$ vertices does not have a Hamiltonian path, because removing the vertex $y$ breaks it into three components.