An Ore graph is a graph that satisfies Ore's theorem, i.e., a graph
for which the sums of the degrees of nonadjacent vertices is greater than or equal
to the number of nodes
for all subsets of nonadjacent vertices. Let be the vertex set and the edge
set of ,
let denote the vertex
count of ,
let denote the vertex degree of vertex by ,
and let
denote a pair of vertices. The condition for to be an Ore graph can then be written

(Ore 1960; Bondy 1971). Note that Skiena (1990, p. 197) and Pemmaraju and Skiena (2003, p. 301) state a weaker version of this result with the "greater or equal than" replaced by "greater than."

Ore's theorem states that Ore graphs are always Hamiltonian. Furthermore, for such graphs, a Hamiltonian cycle can be constructed in polynomial
time (Bondy and Chvátal 1976; Skiena 1990, p. 197). The numbers of
graphs on ,
2, ... satisfying Ore's criterion (using the "vacuous truth" convention
and so including complete graphs ) are 1, 1, 1, 3, 5, 21, 68, 503, 4942, 128361, ... (OEIS
A264683), the first few of which are illustrated
above.

Every graph satisfying Ore's criterion is Hamiltonian, but not every Hamiltonian graph satisfies the
criterion. The numbers of simple Hamiltonian graphs on , 2, ... vertices that do not satisfy Ore's criterion are
0, 0, 0, 0, 3, 27, 315, 5693, 172141, 9176757, ... (OEIS A264684),
the first few of which are illustrated above.

Bondy, J. A. "Pancyclic Graphs I." J. Combin. Th.11, 80-84, 1971.Bondy, J. A. and Chvátal,
V. "A Method in Graph Theory." Disc. Math.15, 111-136, 1976.Meyniel,
M. "Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe
orienté." J. Combin. Th.14, 137-147, 1973.Ore,
O. "A Note on Hamiltonian Circuits." Amer. Math. Monthly67,
55, 1960.Palmer, E. M. "The Hidden Algorithm of Ore's Theorem
on Hamiltonian Cycles." Computers Math. Appl.34, 113-119, 1997.Pemmaraju,
S. and Skiena, S. Computational
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge,
England: Cambridge University Press, 2003.Skiena, S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequences A264683
and A264684 in "The On-Line Encyclopedia
of Integer Sequences."Woodall, D. R. "Sufficient Conditions
for Circuits in Graphs." Proc. London Math. Soc.24: 739-755,
1972.