Dirac’s Theorem at a Dinner Party

Gabriel Dirac (the famous graph theorist) was the stepson of Paul Dirac (the even more famous physicist). Paul Dirac spent the last years of his career at Florida State University, and my father took his course in General Relativity in the 1970s.

Gabriel formulated an important theorem about Hamiltonian cycles. In this post I want to give a refresher on Hamiltonian cycles, and go over a fun proof of his theorem that involves a hypothetical dinner party.

Over the course of several decades, Dirac’s theorem was improved when mathematicians formulated similar theorems that work with a broader range of graphs. In the following figure, each theorem is more general than the one to its left. Each graph meets its own theorem’s condition, but none of the ones to its left, and its Hamiltonian cycle is blue.

A Hamiltonian cycle is a walk along the edges of a graph that visits every vertex exactly once and ends up back where it started. A graph that has one is Hamiltonian.

Hamiltonian cycles are related to the Traveling Salesman Problem (e.g. designing delivery routes for Amazon packages). But my personal favorite application is an old-school computer graphics problem: given a triangle mesh, can you render it using a single triangle strip?

Intuitively, it should be easier to find a Hamiltonian cycle in a graph that has lots of edges relative to its vertex count. In a way, that intuition is what Dirac formalized:

The following figure shows a random graph with 10 vertices, where every vertex has exactly 5 neighbors, so the theorem guarantees a Hamiltonian cycle. On the right, the same graph has been rearranged so that its Hamiltonian cycle runs around the outside…like a circular dinner table.

1. Dinner party

To see why the theorem is true, first imagine a party where each guest is a vertex and each friendship is an edge. Friendship goes both ways, and nobody is their own friend, which is what simple means in graph theory. A Hamiltonian cycle is a way to seat everyone at a round table so that each guest sits between two friends:

Here’s the plan. Seat everyone in random order. Two guests who sit side by side are seatmates, and they might be friends, or strangers. Seatmates who are friends get a blue edge, and other friends get a gray edge. Seatmates who are strangers make a gap, which gets a dotted orange line. Here’s the graph from before as a party, seated in random order, with four gaps:

So, if we can find a way that always gets rid of all the gaps, then we will have shown that the theorem is true. We’ll do it with a sequence of moves somewhat akin to playing musical chairs.

2. Musical chairs

Say that strangers and sit side by side, with just clockwise of . And say that somewhere else at the table, there are two more seatmates, and , with just clockwise of , where is a friend of , and is a friend of .

Here’s the move: everyone from clockwise around to stands up, and sits back down in the reverse order. That’s a flip. Afterward, sits next to , and sits next to , and those are both pairs of friends.

In the following figure, the stretch that flips is shaded blue. Drag the slider under it to watch it flip.

Why is Lemma 1 true? Inside the stretch that flips, each guest has the same two seatmates as before, just on opposite sides. So the only seatmates who change are at the two endpoints. Before the flip, those were and , who are strangers, and and . After the flip, they’re and , and and , who are friends. (If and were strangers too, then the flip closes two gaps at once.)

The friendship of and , and the friendship of and , cross like an X. Let’s call a pair of friendships like that a crossing: one from to , and one from to the guest just clockwise of . Each crossing gives a flip.

The following interactive figure runs the algorithm on the party from before, starting with the seating arrangement that happens to have four gaps, and flips until there are none.

Here’s the algorithm:

seat everyone in any order
while some strangers u and v sit side by side, with v just clockwise of u:
    find a friend x of u who sits just counterclockwise of a friend y of v
    reverse the order of everyone from v around to x

So the whole proof comes down to one question. Do gaps always have corresponding crossings? In the next section we’ll answer that question.

3. Pass the potatoes

Recall that is the number of guests at the party. Let’s write for the number of friends of guest . Here’s what we seek to prove:

One way to see how this is true is the following thought experiment. Give a red potato to each friend of , and a Yukon Gold to each friend of . That’s potatoes, which is at least . Then everyone with a red potato passes it one seat clockwise, like this:

After that, note that can no longer hold any potatoes. So the other guests hold all of the potatoes. Therefore, since there are at least total potatoes, some guest holds two.

Let’s use to refer to a guest with two potatoes (circled above). They have a Yukon Gold, so is a friend of . The red one came from the guest just counterclockwise of , who is a friend of , and that’s . That’s the crossing.

Back to Dirac’s theorem. If every guest has at least friends, then for any two strangers, , so every gap has a crossing (Lemma 2). Each flip closes a gap and opens none (Lemma 1), so the number of gaps drops with every flip, until there are none, and everyone sits between two friends.

4. References

Edgar Palmer discovered this proof in the work of Øystein Ore and wrote about it in The hidden algorithm of Ore’s theorem on Hamiltonian cycles (though he did not use dinner tables and potatoes).

Dirac’s theorem first appeared in his paper Some theorems on abstract graphs, in the Proceedings of the London Mathematical Society in 1952.