Жемчужина Эйлера

На типичной карте могут встречаться страны, имеющие много соседей, но это невозможно для всех стран сразу. На любой карте найдется страна, имеющая пять или менее соседей. Этот важный факт называется теоремой о пяти соседях. Для его доказательства нужна формула Эйлера и немного арифметики. В терминах теории графов она формулируется так:

Теорема о пяти соседях

В каждом простом планарном графе существует вершина степени 5 или меньше.

Пусть имеется простой планарный граф. Поскольку в нем нет петель и параллельных ребер, можно добавить ребра так, что каждая грань будет ограничена ровно тремя ребрами. Мы докажем, что этот (больший) триангулированный граф содержит вершину степени 5 или меньше, а потому такая вершина должна быть и в (меньшем) исходном графе. Предположим, что триангулированный граф имеет V вершин, E ребер и F граней (внешняя область считается гранью). Каждое ребро является общей границей двух граней, а каждая грань ограничена тремя ребрами, поэтому 3F = 2E. По формуле Эйлера, V — E + F = 2, или, эквивалентно, 6E — 6F = 6V — 12. Подставляя 4E вместо 6F, получаем

2E = 6V — 12.

Поскольку у каждого ребра два конца, сумма степеней всех вершин равна 2E. Поэтому средняя степень вершин равна

Так как средняя степень меньше шести, то должна существовать по меньшей мере одна вершина степени 5 или меньше.

Чтобы продемонстрировать полезность теоремы о пяти соседях в задачах раскрашивания графов, докажем теорему о шести красках.

Теорема о шести красках

Любую карту можно раскрасить шестью или меньшим количеством цветов.

Предположим, что это утверждение неверно. Тогда найдется одна или несколько карт, которые нельзя раскрасить шестью цветами. Найдем в этом множестве «плохих» карт карту с наименьшим числом стран. Пусть число стран на этой карте равно N. Такой наименьший контпример часто называют минимальным злодеем. Польза выделения минимального злодея в том, что можно с уверенностью сказать, что любую карту, содержащую N — 1 или меньше стран, можно раскрасить шестью цветами.

Рассмотрим граф смежности G минимального злодея. По теореме о пяти соседях, в G найдется вершина v степени 5 или меньше. После удаления v и всех инцидентных ей ребер из G получится новый граф H. Легко видеть, что H является графом смежности карты с N — 1 странами. Поскольку H содержит N — 1 вершин, его можно раскрасить шестью цветами. Теперь вернем удаленную вершину вместе с ребрами в граф. Поскольку v соседствует не более чем с 5 другими вершинами, найдется хотя бы один неиспользованный цвет, которым можно покрасить v. Таким образом, G можно раскрасить в шесть цветов. Это противоречит предположению о том, что G — минимальный злодей, а следовательно, любая карта допускает 6-раскраску. На рис. 14.6 эта техника использована для раскрашивания графа в красный, синий, зеленый, фиолетовый и оранжевый цвета.

Рис. 14.6. Раскрашивание минимального злодея шестью цветами

К сожалению, это доказательство не проходит, когда число доступных цветов равно 4 или 5. Когда придет время вставить вершину v обратно, может не оказаться свободного цвета для ее окрашивания. В этих случаях нужны более тонкие рассуждения.

Одно такое рассуждение придумал Альфред Брей Кемпе (1849–1922). 17 июля 1879 года Кемпе, ученик Кэли, объявил, что нашел доказательство гипотезы четырех красок, и это доказательство было опубликовано в том же году¹¹⁸.

Рис. 14.7. Альфред Брей Кемпе

В отличие от большинства неверных доказательств, найденных за последующие сто лет, доказательство Кемпе было очень убедительным. Он предложил несколько новых остроумных методов, что позволило ему покрасить последнюю оставшуюся вершину минимального злодея. Математическое сообщество было взбудоражено.

Доказательство Кемпе оставалось последним словом в гипотезе четырех красок на протяжении десяти лет. Но, к сожалению для Кемпе, дело не было закрыто. В 1889 году Перси Джон Хивуд (1861–1955) нашел ошибку в рассуждениях Кемпе. И она оказалась фатальной. Хивуд предъявил пример карты, для которой аргументация Кемпе потерпела крах. В публикации, появившейся в 1890 году, Хивуд писал:

Настоящая статья не претендует на доказательство исходной Теоремы; на самом деле ее цели скорее деструктивные, чем конструктивные, т. к. будет показано, что в общепризнанном доказательстве имеется дефект¹¹⁹.