Graph theory haiku

Ore’s Theorem

A red-blue Kn:
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 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 v1v2vnv1.

A graph with blue edges and its complement in red.

Consider the blue neighbours of v1 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 dG(v1) of these vertices, and if v1v2 is red (i.e. v1 and v2 are nonadjacent in G), then the theorem’s hypothesis tells us that

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

Since v2 has only n−1−dG(v2) red neighbours and is not itself in S, that means at least one vertex vi+1 in S is a blue neighbour of v2. We can now replace v1v2 and vivi+1 in the cycle with the two blue edges v1v2 and v2vi+1 to get a Hamilton cycle of Kn with at least one more blue edge than we had before.

Switching two edges on the Hamilton cycle to create another Hamilton cycle with more blue edges.

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

Pages: 1 2 3 4