Necessary vs. Sufficient Conditions for Hamiltonian Cycles
You'll learn why finding Hamiltonian cycles is tricky and meet two powerful sufficient conditions that guarantee their existence.
The Challenge
Unlike Eulerian circuits (which have a clean necessary and sufficient condition based on vertex degrees), no simple necessary and sufficient condition exists for determining whether a graph contains a Hamiltonian cycle. This is one of graph theory's frustrating mysteries—deciding if a Hamiltonian cycle exists is actually a famously difficult computational problem (NP-complete).
However, mathematicians have discovered sufficient conditions—rules that, when satisfied, guarantee a Hamiltonian cycle exists, even though they're not required for one to exist.
Dirac's Theorem (1952)
If a simple graph has n ≥ 3 vertices and every vertex has degree at least n/2, then the graph contains a Hamiltonian cycle.
Think of it like this: If everyone at a party knows at least half the other guests, you can arrange them in a circle where each person stands next to someone they know.
Example: A graph with 8 vertices where every vertex has degree ≥ 4 must have a Hamiltonian cycle.
Ore's Theorem (1960)
A more flexible condition: If a simple graph has n ≥ 3 vertices and for every pair of non-adjacent vertices u and v, deg(u) + deg(v) ≥ n, then the graph contains a Hamiltonian cycle.
Ore's theorem is weaker (more general) than Dirac's—it catches graphs that Dirac's might miss because it only requires the degree sum condition for non-neighbors.
Key Takeaway: No simple test determines Hamiltonian cycles definitively, but Dirac's and Ore's theorems provide strong sufficient conditions—if their degree requirements hold, a Hamiltonian cycle is guaranteed to exist.