# Ore's Theorem haiku

A red-blue $K_n$:
bluest Hamilton circuit
lies fully in $G$.

Ore's theorem states:

Let $G$ be a simple graph on $n ≥ 3$ vertices such that $d(u)+d(v) ≥ n$ for any nonadjacent $u,v$. Then $G$ 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 $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 \ldots v_n v_1$. A graph satisfying the theorem's conditions (left) and a Hamilton cycle in the red-blue KnK_nKn​ (right).

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) ≥ 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_i$ 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. 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 $K_n$ with no red edges. The cycle being blue means it lies entirely in $G$, which proves the theorem.