Condition for Existence of Hamilton Cycles
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).