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 Proof Method Classification
Statement Form Ore's Theorem
Filter Results1 entry
Connections
Has Statement Form
In Branch
Principal Result Of
Source Ore's Theorem (Wikipedia)
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.
Principal Result Of: Øystein Ore, Lead sentence of the article on the result
Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore.
View the Source 2. ProofWiki: Ore's Theorem
ProofWikiProof sectionQuote, Proof section
Aiming for a contradiction, suppose it were possible to construct a graph that fulfils condition $(1)$ which is not Hamiltonian.
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.