Ore’s theorem

Let G be a simple graphMathworldPlanetmath of order n3 such that, for every pair of distinct non adjacent vertices u and v, deg(u)+deg(v)n. Then G is a Hamiltonian graphMathworldPlanetmath.

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