Proving a graph does not have a hamilton circuit

124 Views Asked by At

enter image description here

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?

1

There are 1 best solutions below

1
On 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.