## Ore’s Theorem

*A red-blue K_{n}: bluest Hamilton circuit lies fully in G.*

Ore’s theorem states:

Let

Gbe a simple graph onn≥3 vertices such that d(u)+d(v)≥nfor any nonadjacentu,v. ThenGcontains a Hamilton cycle.

Bondy’s proof is roughly as follows. Colour the edges of G blue and add red edges to make a complete graph. The complete graph on *n*** **≥** **3 vertices has no shortage of Hamilton cycles, so choose one and label it *v*_{1}*v*_{2}…*v*_{n}*v*_{1}.

Consider the blue neighbours of *v*_{1} on the cycle, and then move one vertex to the right along the cycle so you’re looking at the set

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

There are d_{G}(*v*_{1}) of these vertices, and if *v*_{1}*v*_{2} is red (i.e. *v*_{1} and *v*_{2} are nonadjacent in *G*), then the theorem’s hypothesis tells us that

|S| = d_G(v_1) \geq n - d_G(v_2).

Since *v*_{2} has only *n*−1−d_{G}(*v*_{2}) red neighbours and is not itself in *S*, that means at least one vertex *v*_{i+1} in *S* is a blue neighbour of *v*_{2}. We can now replace *v*_{1}*v*_{2} and *v*_{i}*v*_{i+1} in the cycle with the two blue edges *v*_{1}*v*_{2} and *v*_{2}*v*_{i+1} to get a Hamilton cycle of *K _{n}* with at least one more blue edge than we had before.

We can make the same argument again and again until we have a Hamilton cycle of *K _{n}* with no red edges. The cycle being blue means it lies entirely in

*G*, which proves the theorem.