I'm reading a book on graph theory, and the book presents the following graph:
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?
Best Answer
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.
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.)