Ore's Theorem haiku

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$.

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.

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.