Sufficient Conditions for the Existence of a Hamiltonian Circuit
Theorem (Ore, 1960): Let G be a graph with n ³3 vertices.
If for each pair, x, y of non-adjacent vertices, deg(x) + deg(y) ³ n,
then G has a Hamiltonian circuit.
Ore's theorem gives a sufficient, but not necessary condition.
Consider any circuit graph with 5 or more vertices.
Corollary (Dirac): If the degree of each vertex is ³ n/2, then G has a Hamiltonian circuit.
Corollary: If G has a pair of non-adjacent vertices x and y, such that deg(x) + deg(y) ³ n,
then G is Hamiltonian if and only if G U {x,y} is Hamiltonian.
The closure of a graph G with n vertices, denoted by c(G), is the graph obtained from G by repeatedly adding edges between non-adjacent vertices whose degrees sum to at least n, until this can no longer be done. Several results concerning the existence of hamiltonian circuits refer to the closure of a graph.
Corollary: G is Hamiltonian iff c(G) is Hamiltonian.
Theorem: Let G be a graph with at least 3 vertices. If c(G) is a complete graph then G is Hamiltonian.