# Why is this graph non-Hamiltonian?

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.

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.
• Why must a cycle be $2$-regular? – user728115 Nov 30 '19 at 20:11
• @hom I added some parenthetical detail to the proof to address your questions. Does that help? – Matthew Daly Nov 30 '19 at 20:15
• Yes it helps, thanks – user728115 Nov 30 '19 at 21:22