# A Simple Graph: A Simple non-Hamiltonian Proof

How does one show that the following graph has no Hamiltonian cycle?

From N.S.'s comment I get that the problem really just reduces to the following simpler problem:

Actually, if you started at the top I guess that wouldn't really be the case... Maybe I should prove this using the $\wedge_{k=1}^np_i\implies q$ method:

Hmm... Maybe it can just be reduced to the following graph instead:

The subgraph $(a,b,c,d)$ is of critical importance here. Without doubt, a tracing along the graph must hit all of these points in the subgraph just mentioned either by exiting through $d$, and then re-entering through $b$ or vice versa. Either way, the tracer must make a choice upon re-entry to make a $(b,a)$-step or $(b,c)$-step, respectively $(d,a)$-step or $(d,c)$-step. Should the tracer take a $(b,a)$-step, respectively $(d,a)$-step, then the tracer will inevitably be trapped as proceeding to vertex $d$, respectively $b$, would mean the tracer hit that vertex twice. Now, if the tracer makes a $(b,c)$-step, respectively $(d,c)$-step, then the tracer will similarly be trapped as the proceeding vertex will have been traced upon twice. Thus, the graph cannot contain a Hamiltonian cycle.

-
The upper (or lower) triangle also immediately shows that there is no Hamiltonian cycle. –  Tomas Aug 2 '13 at 22:53
I don't know if it makes it easier, but you could reduce it to a 3-SAT problem and show that all clauses can't be satisfied. –  kba Aug 2 '13 at 22:57
Here, the central line must be crossed. –  Trancot Aug 2 '13 at 23:03
You don't need a start point. The triangle at the top must be part of a cycle, same for the triangle at the bottom. But a cycle cannot contain a strictly smaller cycle. –  N. S. Aug 2 '13 at 23:03
Just color the edges which pass through the vertices of degree 2 with red, then you`ll see the solution..... –  N. S. Aug 2 '13 at 23:04

Hint Assume by contradiction that the graph has a Hamiltonian cycle. Then the cycle must contain the four vertices of degree $2$ and there is only one way to visit each of those. Those give you 8 edges in the cycle, but for obvious reasons those 8 edges are not part of one cycle....
Added I argued above that the red edges below must be part of the Hamiltonian cycle. Then the Hamiltonian cycle would contain two smaller $4$-cycles, which is impossible (a cycle cannot contain a smaller cycle as a subgraph).