Ore's Theorem

Author

Eric W. Weisstein
December 3, 2015

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/OresTheorem.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/OresTheorem.html.

©2015 Wolfram Research, Inc. except for portions noted otherwise

Code

OreCriteronQ[g_System`Graph,op_:GreaterEqual]:=Module[
{
d=VertexDegree[g],
n=VertexCount[g],
pairs=Complement[Subsets[VertexList[g],{2}],List@@@EdgeList[g]]
},
If[n<3||pairs==={}, (* {} handles complete graphs (which have no nonadjacent vertices and are trivially Hamiltonian),because they "satisfy" the criterion as written in Mathematica via Total/@{} -> {} and Min[{}] -> ∞ *)
False,
op[Min[Total/@(pairs/.Thread[Range[n]->d])],n]
]
]

Check

Satisfies Ore criterion but nonhamiltonian

With[{n=50},Complement[
Select[GraphData[;;n],
OreCriteronQ[GraphData[#]]&],GraphData["Hamiltonian",;;n]]
]//Timing

With[{n=50},Complement[
Select[GraphData[;;n],
OreCriteronQ[GraphData[#],Greater]&],GraphData["Hamiltonian",;;n]]
]//Timing