Ore's Theorem haiku
bluest Hamilton circuit
lies fully in .
Ore's theorem states:
Let be a simple graph on vertices such that for any nonadjacent . Then 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 blue and add red edges to make a complete graph. The complete graph on vertices has no shortage of Hamilton cycles, so choose one and label it .
Consider the blue neighbours of on the cycle, and then move one vertex to the right along the cycle so you're looking at the set
There are of these vertices, and if is red (i.e. and are nonadjacent in ), then the theorem's hypothesis tells us that
Since has only red neighbours and is not itself in , that means at least one vertex in is a blue neighbour of . We can now replace and in the cycle with the two blue edges and to get a Hamilton cycle of 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 with no red edges. The cycle being blue means it lies entirely in , which proves the theorem.