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

Хотя доказательство Кемпе оказалось неправильным, предложенная им техника очень важна. Хивуд признал, что идей Кемпе достаточно для доказательства теоремы о пяти красках. Более того, они вошли неотъемлемой частью в окончательное доказательство теоремы о четырех красках. И хотя неверное доказательство стало ударом по репутации Кемпе, окончательно его карьеру оно не подорвало. Он остался активным членом Лондонского королевского общества (в которое был избран за математические работы, не относящиеся к теореме о четырех красках), а впоследствии был возведен в рыцари.

Всякий, кто пытался раскрасить большую карту в четыре цвета, знает, что поначалу все идет легко, но в какой-то момент оказывается, что дальнейшее раскрашивание невозможно[8]. В этот момент приходится вернуться и перекрасить части карты в другие цвета. Прием, придуманный Кемпе, дает простой способ перекрасить карту.

Начнем с любого раскрашенного (или частично раскрашенного) графа. Выберем два цвета, скажем красный (R) и синий (B), и вершину, покрашенную в один из них. Проследуем по всем возможным путям из этой вершины, которые проходят через синюю вершину, потом красную, затем синюю и т. д. Это множество красных и синих вершин называется красно-синей цепочкой, или цепочкой Кемпе (см. рис. 14.8). Заметим, что цепочка Кемпе часто нелинейная, в ней могут быть ветвления или циклы. Ключевое наблюдение состоит в том, что поскольку никакая вершина, смежная с цепочкой Кемпе, не может быть ни красной, ни синей, мы можем перекрасить каждую красную вершину в цепочке в синий цвет и наоборот, и полученная раскраска графа по-прежнему будет правильной.

Рис. 14.8. Перестановка цветов в красно-синей цепочке дает еще одну допустимую раскраску

Выше мы доказали теорему о шести красках. А прием Кемпе позволит нам доказать теорему о пяти красках.

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

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

Начнем доказательство точно так же, как для теоремы о шести красках. Предположим, что имеется минимальный злодей — карта с наименьшим количеством стран N, которую нельзя раскрасить пятью красками. По теореме о пяти соседях, в графе смежности G существует вершина v степени 5 или меньше. Обозначим H граф, полученный удалением вершины v. Поскольку H содержит N — 1 вершин, его можно раскрасить в пять красок. Рассмотрим вершины, соседние с v. Если для раскрашивания этих вершин использовано 4 или меньше красок (например, если степень v не больше 4), то раскраску можно завершить, выбрав для окрашивания v неиспользованный цвет. Но если для раскрашивания вершин, соседних с v, использованы все пять цветов, то решение не такое простое.

Назовем a, b, c, d, e вершины, соседние с v (перечислены по часовой стрелке), и предположим, что они раскрашены в красный, синий, желтый, зеленый и фиолетовый цвета. Рассмотрим красную вершину a и содержащую ее красно-желтую цепочку. Необходимо рассмотреть два случая. Сначала предположим, что вершина c не принадлежит этой красно-желтой цепочке (как на рис. 14.9). Тогда мы можем переменить цвета красных и желтых вершин в цепочке на противоположные, не меняя цвета вершины c. В частности, мы сможем покрасить v красным и получить 5-раскраску G. С другой стороны, предположим, что c принадлежит красно-желтой цепочке (как на рис. 14.10). Тогда перемена цветов в цепочке изменила бы и цвет c, поэтому для v не освободился бы цвет. Это нам ничего бы не дало. Однако поскольку граф планарный, сине-зеленая цепочка, содержащая вершину d, не может содержать вершину b. Поэтому перемена цветов в этой сине-зеленой цепочке позволяет покрасить v зеленым цветом, и мы получим 5-раскраску G.

Рис. 14.9. Перестановка цветов в красно-желтой цепочке для завершения раскраски

Рис. 14.10. Перестановка цветов в сине-зеленой цепочке для завершения раскраски

Дефектное доказательство Кемпе теоремы о четырех красках было похоже на это доказательство теоремы о пяти красках. Но рассуждение было по необходимости более тонким. Может случиться, что вершина v степени 5 окружена вершинами четырех разных цветов. Пришлось бы перекрасить одну или две цепочки Кемпе, чтобы уменьшить это число до трех и покрасить v. Но хотя этот метод, на первый взгляд, кажется корректным, был упущен один случай, когда перекрашивание двух цепочек Кемпе дает недопустимую раскраску.

Популярность этой завораживающей задачи продолжала увлекать как профессиональных математиков, так и любителей. Такие известные математики, как Джордж Д. Биркгоф (1884–1944), Хасслер Уитни (1907–1989), Анри Лебег (1875–1941) и Освальд Веблен (1880–1960), приняли этот вызов. Несмотря на длинные послужные списки, гиганты не смогли расколоть этот трудный орешек. Некоторые авторитетные математики, например Г. С. М. Кокстер, даже выражали сомнение в правильности гипотезы.