Ore's theorem

We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if then G is Hamiltonian.

Palmer (1997) describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition.

Each step increases the number of consecutive pairs in the cycle that are adjacent in the graph, by one or two pairs (depending on whether vj and vj + 1 are already adjacent), so the outer loop can only happen at most n times before the algorithm terminates, where n is the number of vertices in the given graph.

Woodall (1972) found a version of Ore's theorem that applies to directed graphs.

A closely related theorem by Meyniel (1973) states that an n-vertex strongly connected digraph with the property that, for every two nonadjacent vertices u and v, the total number of edges incident to u or v is at least 2n − 1 must be Hamiltonian.

A graph meeting the conditions of Ore's theorem, and a Hamiltonian cycle in it. There are two vertices with degree less than n /2 in the center of the drawing, so the conditions for Dirac's theorem are not met. However, these two vertices are adjacent, and all other pairs of vertices have total degree at least seven, the number of vertices.
Illustration for the proof of Ore's theorem. In a graph with the Hamiltonian path v 1 ... v n but no Hamiltonian cycle, at most one of the two edges v 1 v i and v i − 1 v n (shown as blue dashed curves) can exist. For, if they both exist, then adding them to the path and removing the (red) edge v i − 1 v i would produce a Hamiltonian cycle.