What Is The Relationship Between Dirac's Theorem And Ore's Theorem?

The relationship between Dirac's theorem and Ore's theorem is that Ore's theorem is a generalization of Dirac's theorem. This means that any graph that satisfies the conditions of Dirac's theorem will also satisfy the conditions of Ore's theorem. Therefore, Dirac's theorem is a direct consequence, or corollary, of Ore's theorem.

Both theorems provide sufficient conditions for an undirected graph to have a Hamiltonian cycle, which is a cycle that visits every vertex exactly once. However, their conditions are different, with Ore's condition being less restrictive.

Understanding the theorems

To fully grasp their relationship, it is important to first understand each theorem individually.

Dirac's theorem (1952)

Dirac's theorem provides a straightforward condition based on the minimum degree of a graph.

Statement: For a simple graph Gcap G

𝐺

with n≥3n is greater than or equal to 3

𝑛≥3

vertices, if the minimum degree of any vertex is at least n/2n / 2

𝑛/2

, then Gcap G

𝐺

is Hamiltonian.
**Condition:**δ(G)≥n2delta open paren cap G close paren is greater than or equal to n over 2 end-fraction

𝛿(𝐺)≥𝑛2

This condition is powerful because it only requires checking the lowest degree in the entire graph. If even the "least connected" vertex is connected to at least half of the other vertices, the graph is guaranteed to have a Hamiltonian cycle.

Ore's theorem (1960)

Ore's theorem, proved eight years after Dirac's, extends this idea by relaxing the condition from all vertices to just pairs of non-adjacent vertices.

Statement: For a simple graph Gcap G

𝐺

with n≥3n is greater than or equal to 3

𝑛≥3

vertices, if for every pair of non-adjacent vertices uu

𝑢

and vv

𝑣

, the sum of their degrees is at least nn

𝑛

, then Gcap G

𝐺

is Hamiltonian.
**Condition:**deg(u)+deg(v)≥ndeg u plus deg v is greater than or equal to n

deg(𝑢)+deg(𝑣)≥𝑛

for all non-adjacent u,v∈V(G)u comma v is an element of cap V open paren cap G close paren

𝑢,𝑣∈𝑉(𝐺)

This condition is less restrictive because it allows for vertices with a degree less than n/2n / 2

𝑛/2

as long as they are adjacent to other vertices with a sufficiently high degree.

Why Ore's theorem generalizes Dirac's theorem

The logical connection between the two theorems can be shown with a simple proof:

Assume Dirac's condition: Let's take a graph Gcap G

𝐺

that satisfies Dirac's theorem, meaning its minimum degree is at least n/2n / 2

𝑛/2

. That is, δ(G)≥n2delta open paren cap G close paren is greater than or equal to n over 2 end-fraction

𝛿(𝐺)≥𝑛2

.
Consider any pair of non-adjacent vertices: Now, let uu

𝑢

and vv

𝑣

be any two non-adjacent vertices in Gcap G

𝐺

.
Apply Dirac's condition: By the definition of the minimum degree, the degree of each of these vertices must be at least the minimum degree.
- deg(u)≥δ(G)≥n2deg u is greater than or equal to delta open paren cap G close paren is greater than or equal to n over 2 end-fraction
  
  deg(𝑢)≥𝛿(𝐺)≥𝑛2
- deg(v)≥δ(G)≥n2deg v is greater than or equal to delta open paren cap G close paren is greater than or equal to n over 2 end-fraction
  
  deg(𝑣)≥𝛿(𝐺)≥𝑛2
Check Ore's condition: If we add these degrees, we get:
- deg(u)+deg(v)≥n2+n2=ndeg u plus deg v is greater than or equal to n over 2 end-fraction plus n over 2 end-fraction equals n
  
  deg(𝑢)+deg(𝑣)≥𝑛2+𝑛2=𝑛
Conclusion: The sum of the degrees of any two non-adjacent vertices in Gcap G

𝐺

is at least nn

𝑛

. This is exactly the condition for Ore's theorem.

Therefore, any graph that satisfies Dirac's theorem automatically satisfies Ore's theorem and is consequently Hamiltonian. However, the reverse is not true. There are Hamiltonian graphs that satisfy Ore's condition but not Dirac's.

The key distinction: A practical example

A graph with n=7n equals 7

𝑛=7

vertices provides a clear example of the distinction between the two theorems.

Dirac's Condition: Requires every vertex to have a degree of at least ⌈7/2⌉=4the ceiling of 7 / 2 end-ceiling equals 4

⌈7/2⌉=4

.
Ore's Condition: Requires that for any two non-adjacent vertices, the sum of their degrees is at least 7.

Consider a graph where two non-adjacent vertices have degrees 3 and 4, and all other vertices have a degree of at least 4.

Does it satisfy Dirac's? No, because the minimum degree is 3, which is less than 4.
Does it satisfy Ore's? Yes, because the sum of the degrees of the non-adjacent vertices is 3+4=73 plus 4 equals 7

3+4=7

, which meets the condition. All other pairs of non-adjacent vertices would have even larger degree sums.

This demonstrates how Ore's theorem can prove a graph is Hamiltonian in cases where Dirac's theorem is inconclusive, making Ore's theorem the more general and powerful statement.

Extensions and generalizations

The relationship between Dirac's and Ore's theorem is a classic example of how mathematical results are refined and generalized. This path of inquiry led to even broader theorems in graph theory.

Bondy–Chvátal Theorem (1971): This theorem further generalizes Ore's result. It defines a "closure" operation on a graph where edges are added between non-adjacent vertices whose degree sum is at least nn

𝑛

. The Bondy–Chvátal theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian. Because a graph satisfying Ore's condition results in a complete graph after closure, and a complete graph is always Hamiltonian, Ore's theorem is an immediate consequence.
Pancyclicity: Adrian Bondy later strengthened Ore's conclusion, showing that with the exception of one specific class of bipartite graphs, any graph meeting Ore's condition is not just Hamiltonian but pancyclic, meaning it contains cycles of every possible length from 3 to nn

𝑛

.

In summary, Dirac's theorem is a foundational result that was later subsumed by the more general and powerful Ore's theorem, which in turn paved the way for even broader theorems in Hamiltonian graph theory.

Enjoyed this article? Share it with a friend.