I'm reading a book on graph theory, and the book presents the following graph:

enter image description here

They justify that the graph is not Hamiltonian as follows:

Let’s suppose that $G$ is Hamiltonian. Then $G$ contains a Hamiltonian cycle $C$. Since $C$ contains the vertex $t$, which has degree $2$, both $tu$ and $tz$ lie on $C$. By the same reasoning, $xy$ and $xz$ lie on $C$, as do $vw$ and $vz$. However, this says that $z$ is incident with three edges on $C$, which is impossible. Therefore, as we claimed, the graph $G$ is not Hamiltonian.

I think the reason why $tu, tz, xy, xz, vw, vz$ must lie on $C$ is because everytime we go into a vertex, we need to come out? I'm not completely sure about this. Now if these edges must be in the cycle, then I see why $z$ is incident with at least three vertices but not why it's incident with exactly $3$ (why can't $yz$ or $wz$ be on $C$)? Finally, let's suppose $z$ was incident with three edges on $C$. I don't see why this makes it impossible for a Hamiltonian cycle to exist.

Can someone please clarify?


We're looking for a Hamilton cycle of $G$, which is a 2-regular subgraph that has the same vertex set as $G$. (A cycle is a closed walk of a graph that doesn't repeat vertices or edges. So each vertex has two edges incident on it. If you like, you might think of a train following the cycle which is "entering" and "exiting" the vertex as it works its way around the cycle.) Assume that such a cycle of $G$ exists.

  • Since the cycle has the same vertex set as $G$, $x$, $t$, and $v$ must be in the cycle as you say.
  • Since the cycle is 2-regular and those three vertices all have degree 2, it must be that $xy,\ xz,\ tu,\ tz,\ vw,\text{ and }vz$ are all edges in the cycle. (As you say, you need to "enter" and "exit" each vertex in a cycle.)
  • But then there are three edges incident on $z$, which means that the cycle cannot be 2-regular. (It doesn't matter if there are extra edges incident on $z$ or not, because there are already too many edges incident on $z$. More still won't fix the problem.)

  • This violates the definition of a cycle. (A cycle is a closed walk that does not repeat vertices or edges. We need to "enter" and "exit" $z$ exactly once, so more than two edges woulc mean that we're "coming back" to $z$. We're not allowed to do that in a cycle.)

  • So by contradiction we conclude that $G$ is not Hamiltonian.
| cite | improve this answer | |
  • $\begingroup$ Why must a cycle be $2$-regular? $\endgroup$ – user728115 Nov 30 '19 at 20:11
  • $\begingroup$ @hom I added some parenthetical detail to the proof to address your questions. Does that help? $\endgroup$ – Matthew Daly Nov 30 '19 at 20:15
  • $\begingroup$ Yes it helps, thanks $\endgroup$ – user728115 Nov 30 '19 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy