Search code examples
discrete-mathematicshamiltonian-cycle

is there a hamiltonian circuit in the graph in the link below?

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

enter image description here

I cant add the picture in here since stackoverflow didnt allow me

Solution

  • 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.