4
$\begingroup$

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. enter image description here

$\endgroup$
  • 1
    $\begingroup$ Hint: Focus on the vertices of degree 2. $\endgroup$ – Chris Culter Feb 24 '16 at 7:05
  • $\begingroup$ Is there a law that I am missing? I see that there are 5 vertices of degree 2, but not sure how I can use that to justify that the graph is not a Hamiltonian. $\endgroup$ – Jebus Crust Feb 24 '16 at 7:26
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.