Ore’s theorem

Let $G$ be a simple graph of order $n\ge 3$ such that, for every pair of distinct non adjacent vertices $u$ and $v$, $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$. Then $G$ is a Hamiltonian graph.

Title	Ore’s theorem
Canonical name	OresTheorem
Date of creation	2013-03-22 11:52:40
Last modified on	2013-03-22 11:52:40
Owner	Koro (127)
Last modified by	Koro (127)
Numerical id	10
Author	Koro (127)
Entry type	Theorem
Classification	msc 05C45
Classification	msc 18D20
Related topic	HamiltonianGraph
Related topic	BondyAndChvatalTheorem