Hello, I am trying to prove that this graph does not have a Hamilton circuit. The only thing I know is that all vertices of degree 2 must have all their edges in the circuit, however this does not prove to be useful. Are there any other useful observations that can be made?
Best Answer
There's two approaches here.
The first is to start from where you started from: the degree-$2$ vertices ($T$ and $P$) must all have their edges in the Hamiltonian cycle. Once you draw those edges, you can keep going with some other vertices. For example, you'll see that vertex $Y$ (which has $3$ edges) can no longer use one of them, so it must use the other two. Repeat until you paint yourself into a corner.
The second is a problem of global structure. The graph is bipartite. Identify how, and then figure out why this prevents a Hamiltonian cycle from existing.