Like the question says in the image in the link.
Is there a hamilton circuit
in the graph above ?
i found some hamilton path
like :
c - b - a -j - i - h - f - e - d - g
But no hamilton circuit
I cant add the picture in here since stackoverflow didnt allow me
There cannot be a hamiltonian cycle.
Proof:
In a hamiltonian cycle, every vertex must be visited and no edge can be used twice. Thus, if a vertex has degree two, both its edges must be used in any such cycle.
a
, c
, and g
are degree two, so it follows that if there is a hamiltonian cycle it must contain the path j - a - b - c - d - g - h
. However, this path does not contain e
but it contains two of e
's neighbors, b
and d
. e
only has one remaining neighbor, f
, so there is no way to extend the path to a hamiltonian cycle that contains e
. Thus there can be no hamiltonian cycle in the graph.