Ore's Theorem haiku

A red-blue KnK_n:
bluest Hamilton circuit
lies fully in GG.

Ore's theorem states:

Let GG be a simple graph on n3n ≥ 3 vertices such that d(u)+d(v)nd(u)+d(v) ≥ n for any nonadjacent u,vu,v. Then GG contains a Hamilton cycle.

Bondy's proofShort proofs of classical theorems. Journal of Graph Theory 44(3). J Adrian Bondy (2003). is roughly as follows. Colour the edges of GG blue and add red edges to make a complete graph. The complete graph on n3n ≥ 3 vertices has no shortage of Hamilton cycles, so choose one and label it v1v2vnv1v_1 v_2 \ldots v_n v_1.

A graph satisfying the theorem's conditions (left) and a Hamilton cycle in the red-blue (right).

Consider the blue neighbours of v1v_1 on the cycle, and then move one vertex to the right along the cycle so you're looking at the set

S={vi+1:v1viE(G)}. S = \{ v_{i+1}: v_1 v_i \in E(G) \}.

There are dG(v1)d_G(v_1) of these vertices, and if v1v2v_1 v_2 is red (i.e. v1v_1 and v2v_2 are nonadjacent in GG), then the theorem's hypothesis tells us that

S=dG(v1)ndG(v2). |S| = d_G(v_1) ≥ n - d_G(v_2).

Since v2v_2 has only n1dG(v2)n - 1 - d_G(v_2) red neighbours and is not itself in SS, that means at least one vertex vi+1v_{i+1} in SS is a blue neighbour of v2v_2. We can now replace v1v2v_1 v_2 and vivi+1v_i v_{i+1} in the cycle with the two blue edges v1viv_1 v_i and v2vi+1v_2 v_{i+1} to get a Hamilton cycle of KnK_n with at least one more blue edge than we had before.

A bluer Hamilton cycle made by swapping edges (left) and an entirely blue cycle found by repeating the process (right).

We can make the same argument again and again until we have a Hamilton cycle of KnK_n with no red edges. The cycle being blue means it lies entirely in GG, which proves the theorem.