If, in a simple graph on n vertices with n at least three, every pair of non-adjacent vertices has degrees summing to at least n, the graph contains a Hamiltonian cycle. Proved by Oystein Ore, it strengthens Dirac's earlier minimum-degree condition for Hamiltonicity.
Facts
StatementIf, in a finite simple graph with n greater than or equal to 3 vertices, every pair of non-adjacent vertices has degrees summing to at least n, then the graph is Hamiltonian. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Proved By
Source Ore's Theorem (Wikipedia)
Sources
1. Ore's Theorem (Wikipedia)
Wikimedia FoundationLead section
the theorem considers the sum of the degrees of pairs of non-adjacent vertices: if every such pair has a sum that at least equals the total number of vertices in the graph, then the graph is Hamiltonian.
Lead section, proof year
Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.