Ore's Theorem
What You'll Learn
You'll discover a powerful shortcut for proving a graph has a Hamiltonian cycle by checking the sum of degrees of non-adjacent vertices.
The Core Idea
After learning Dirac's Theorem, which requires every vertex to have degree at least n/2, you might wonder if there's a more flexible condition. Ore's Theorem provides exactly that.
Ore's Theorem states: If a simple graph has n vertices (where n ≥ 3), and for every pair of non-adjacent vertices u and v, the sum of their degrees satisfies:
deg(u) + deg(v) ≥ n
then the graph is Hamiltonian (it contains a Hamiltonian cycle).
Why This Matters
Ore's Theorem is less restrictive than Dirac's Theorem. While Dirac requires each individual vertex to have high degree, Ore only demands that pairs of non-connected vertices have sufficiently large combined degrees. A vertex could have degree less than n/2, as long as every vertex it's not connected to compensates with a high enough degree.
An Analogy
Think of organizing a round-trip tour visiting all cities exactly once. Dirac's rule says "every city must have many direct flights." Ore's more flexible rule says "if two cities don't have a direct connection, together they must have enough total connections to other cities to make the tour possible anyway."
Checking the Condition
For a graph with n vertices, you examine every pair of vertices that don't share an edge. If their degree sum is at least n for all such pairs, Ore's Theorem guarantees a Hamiltonian cycle exists.
Key Takeaway: Ore's Theorem guarantees a Hamiltonian cycle when every pair of non-adjacent vertices has a combined degree of at least n, offering a more flexible sufficient condition than requiring high individual degrees.