[Math] Graph Theory: How do we know Hamiltonian Path exists in graph where every vertex has degree ≥3

graph theoryhamiltonian-path

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.

Best Answer

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.

Related Question