Ore and Dirac Theorems

Graph Theory · Axiom Academy

Sufficient conditions for Hamiltonian cycles in graphs Let G be a graph with n vertices where n 3. If every vertex has degree at least n/2, then G contains a Hamiltonian cycle. In other words: if deg(v) n/2 for all vertices v, the graph must be Hamiltonian. Example: A graph with 8 vertices where every vertex has degree at least 4 is guaranteed to have a Hamiltonian cycle. Let G be a graph with n vertices where n 3. If for every pair of non-adjacent vertices u and v, we have deg(u) + deg(v) n, then G contains a Hamiltonian cycle. Ore's theorem is a generalization of Dirac's theorem. It checks pairs of non-adjacent vertices instead of requiring high degree for every single vertex. Key insight: A vertex with low degree can still satisfy Ore's condition if its non-neighbors have high degrees. 3. Why Ore's Theorem Generalizes Dirac's We can prove that Dirac's theorem is a special case of Ore's theorem. Proof: Suppose deg(v) n/2 for all vertices v (Dirac's condition). Take any two non-adjacent vertices u and v. Then: This satisfies Ore's condition! Therefore, Dirac's theorem follows from Ore's theorem. This shows that Ore's theorem is strictly more general - it can detect Hamiltonian graphs that Dirac's theorem cannot. 4. Sufficient but Not Necessary Both theorems provide sufficient conditions - if the conditions hold, the graph is definitely Hamiltonian. However, they are not necessary - a graph can be Hamiltonian without satisfying these conditions.

This is the written version of the interactive lesson above. See the full Graph Theory course.