Dirac's theorem, proven with a dinner party and a plate of potatoes

Dirac's Theorem at a Dinner Party

Dirac's theorem, proven with a dinner party and a plate of potatoes

Gabriel Dirac's 1952 theorem guarantees a Hamiltonian cycle whenever every vertex in a graph has at least half as many neighbors as there are vertices. The proof becomes intuitive when guests are vertices and friendships are edges: seat everyone at a round table, then repeatedly flip stretches of the seating to close gaps between strangers. A potato-passing argument shows every gap always has a matching crossing, so the flips never stop until each guest sits between two friends.

Give a red potato to each friend of u, and a Yukon Gold to each friend of v. That's at least n potatoes. Then everyone with a red potato passes it one seat clockwise.

More from this day

2026-11-22