Теорема Дирака за обеденным столом: как картофель доказывает гамильтонов цикл
Dirac's Theorem at a Dinner Party

Габриэль Дирак сформулировал теорему: если в графе с n вершинами каждая вершина смежна хотя бы с n/2 другими, то граф содержит гамильтонов цикл. Автор пересказывает остроумное доказательство через метафору званого ужина: гости — вершины, дружба — рёбра, а рассадка за круглым столом — искомый цикл. Алгоритм «музыкальных стульев» переворачивает отрезки, закрывая разрывы между незнакомцами, а мысленный эксперимент с красной и золотой картошкой доказывает, что каждый разрыв имеет соответствующее пересечение. В конце упоминается гипотеза Барнетта.
Если у каждого гостя не менее n/2 друзей, то для любых двух незнакомцев число друзей гарантирует пересечение, так что каждый разрыв можно закрыть.