Одно такое рассуждение придумал Альфред Брей Кемпе (1849–1922). 17 июля 1879 года Кемпе, ученик Кэли, объявил, что нашел доказательство гипотезы четырех красок, и это доказательство было опубликовано в том же году118.
Рис. 14.7. Альфред Брей Кемпе
В отличие от большинства неверных доказательств, найденных за последующие сто лет, доказательство Кемпе было очень убедительным. Он предложил несколько новых остроумных методов, что позволило ему покрасить последнюю оставшуюся вершину минимального злодея. Математическое сообщество было взбудоражено.
Доказательство Кемпе оставалось последним словом в гипотезе четырех красок на протяжении десяти лет. Но, к сожалению для Кемпе, дело не было закрыто. В 1889 году Перси Джон Хивуд (1861–1955) нашел ошибку в рассуждениях Кемпе. И она оказалась фатальной. Хивуд предъявил пример карты, для которой аргументация Кемпе потерпела крах. В публикации, появившейся в 1890 году, Хивуд писал:
Настоящая статья не претендует на доказательство исходной Теоремы; на самом деле ее цели скорее деструктивные, чем конструктивные, т. к. будет показано, что в общепризнанном доказательстве имеется дефект119.
Хотя доказательство Кемпе оказалось неправильным, предложенная им техника очень важна. Хивуд признал, что идей Кемпе достаточно для доказательства теоремы о пяти красках. Более того, они вошли неотъемлемой частью в окончательное доказательство теоремы о четырех красках. И хотя неверное доказательство стало ударом по репутации Кемпе, окончательно его карьеру оно не подорвало. Он остался активным членом Лондонского королевского общества (в которое был избран за математические работы, не относящиеся к теореме о четырех красках), а впоследствии был возведен в рыцари.
Всякий, кто пытался раскрасить большую карту в четыре цвета, знает, что поначалу все идет легко, но в какой-то момент оказывается, что дальнейшее раскрашивание невозможно[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.
8
Стивен Барр предложил в связи с этим игру для двоих. Первый игрок рисует страну и раскрашивает ее в один из четырех цветов. Второй игрок добавляет страну и тоже раскрашивает ее. Так продолжается до тех пор, пока какой-то игрок не будет вынужден использовать пятый цвет120.