Course contentsShow
← Mathematics
Lesson 2686 of 3,12153. Graph TheoryFree lesson

Ore's Theorem

If for every pair of non-adjacent vertices u, v, deg(u) + deg(v) ≥ n, then the graph is Hamiltonian.

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.