Condition for Existence of Hamilton Cycles

From ProofWiki
Jump to navigation Jump to search

Open Question

Does there exist a simple necessary and sufficient condition for a graph to have a Hamilton cycle?

There is no known criterion for testing whether or not a graph is Hamiltonian.


However, see Ore's Theorem and its corollary Dirac's Theorem for a sufficient conditon (albeit weak).