How To Tell If A Graph is A Hamiltonian?

Question

So, I can look at this graph and tell that it is not a Hamiltonian, but I do not know the actual mathematical reason why. I can see that if you start on one vertex, then it would be impossible to touch every other vertex just once because you would not be able to make it back. So I know that it is not, but I am having trouble explaining why in a way that makes sense.

Answer 1

To say that a graph is Hamilton, we have to find a circuit in the graph that visits each vertex once.

Simple and fundamental rule:

(1).We can construct a Hamilton circuit by starting at the vertex which has degree 2, because all vertices must be in one part of the Hamilton circuit and be visited once, so the degree of 2 force that we should use both of the two edges connected to that vertex of degree 2, one edge for getting into the vertex, and another for leaving out the vertex.

(2).By (1), if we have used two edges of that vertex, then we can't use the other edges connected to that vertex.

By using the simple rules above, if we met the following conditions, then the graph is not Hamilton:

(1).If this way can't avoid to produce a subcircuit(a circuit that doesn't visit all vertices), then we can conclude that the graph is not Hamilton.

(2).After all the possible edges are being used, if there are some vertices that become isolated(didn't connect to any other vertices), then the graph is failure to be Hamilton.

The graph you provided in above: Consider all the degree two verticies of the smaller pentagon in the inside, we have to use all the edges in that pentagon due to that there are five vertices of degree two, and that produce a subcircuit, which is failure to be Hamilton.