Check if graph is Hamiltonian?

1.1k Views Asked by At

I am unable to determine whether the graph below is Hamiltonian. Following a circuit 1-2-3-6-5-4-1 appears to make it a Hamiltonian graph. However the graph does not meet either Dirac's criteria or Ore's criteria. I would request guidance on the ambiguity.

enter image description here

1

There are 1 best solutions below

0
On

If you can show a circuit that visits every vertex once then returns to the first vertex - as you have here - you have proven that the graph is Hamiltonian.

Dirac's and Ore's theorems describe the threshold for graphs that have so many edges that they must be Hamiltonian, even without directly demonstrating a qualifying circuit. The threshold for those cases has to be high enough to ensure that the graph is biconnected, i.e that cut-vertices and cut-edges are excluded (although biconnectedness alone does not guarantee a Hamiltonian circuit).