Рис. 14.9. Перестановка цветов в красно-желтой цепочке для завершения раскраски
Рис. 14.10. Перестановка цветов в сине-зеленой цепочке для завершения раскраски
Дефектное доказательство Кемпе теоремы о четырех красках было похоже на это доказательство теоремы о пяти красках. Но рассуждение было по необходимости более тонким. Может случиться, что вершина v степени 5 окружена вершинами четырех разных цветов. Пришлось бы перекрасить одну или две цепочки Кемпе, чтобы уменьшить это число до трех и покрасить v. Но хотя этот метод, на первый взгляд, кажется корректным, был упущен один случай, когда перекрашивание двух цепочек Кемпе дает недопустимую раскраску.
Популярность этой завораживающей задачи продолжала увлекать как профессиональных математиков, так и любителей. Такие известные математики, как Джордж Д. Биркгоф (1884–1944), Хасслер Уитни (1907–1989), Анри Лебег (1875–1941) и Освальд Веблен (1880–1960), приняли этот вызов. Несмотря на длинные послужные списки, гиганты не смогли расколоть этот трудный орешек. Некоторые авторитетные математики, например Г. С. М. Кокстер, даже выражали сомнение в правильности гипотезы.
Наступил XX век, и внимание ученых обратилось к неизбежным множествам и приводимым конфигурациям. Неизбежным множеством называется набор конфигураций, из которых по меньшей мере одна должна присутствовать в каждом графе смежности. Например, теорема о пяти соседях дает простейшее неизбежное множество, показанное на рис. 14.11, — должна существовать вершина степени меньше 6.
Рис. 14.11. Неизбежное множество конфигураций
С другой стороны, приводимой конфигурацией называется набор вершин и ребер, которые не могут встречаться в минимальном злодее. Используя метод цепочек Кемпе, легко показать, что первые четыре конфигурации на рис. 14.11 приводимые. Мы можем удалить вершину, раскрасить оставшийся граф, при необходимости перекрасить его один раз с помощью цепочек Кемпе, а затем покрасить последнюю вершину. Пятая конфигурация составляет проблему.
Таким образом, целью стало нахождение неизбежного множества неприводимых конфигураций. Сделав это, мы доказали бы теорему о четырех красках, потому что это был бы набор конфигураций, которые не могут встречаться в минимальном злодее, но должны встречаться в любом графе смежности. Это противоречило бы существованию минимального злодея.
22 июля 1976 г., спустя почти сто лет после ошибочного доказательства Кемпе, два исследователя из Иллинойского университета, Кеннет Аппель (1932–2013) и Вольфганг Хакен (родился в 1928 г.), объявили, что нашли неизбежное множество, содержащее 1936 приводимых конфигураций. К моменту появления своих двух статей в следующем году они сумели упростить работу, исключив избыточность и уменьшив количество до 1482121. (Они также добавили в одну из статей третьего автора, Джона Коха, за помощь в вычислениях.) Теорема о четырех красках наконец-то пала!
В конце лета 1976 года Хакен представил свою работу на совместном собрании Американского математического общества и Математической ассоциации Америки. В конце лекции аудитория не разразилась бурными аплодисментами, не было слышно радостных возгласов, и никто с энтузиазмом не похлопывал Хакена по спине. Раздались лишь вежливые хлопки. Для собравшихся в зале математиков-теоретиков так долго ожидаемая развязка одной из самых интересных историй в математике оказалась в высшей степени разочаровывающей.
Причина такого холодного приема заключалась в том, что после того как Аппель и Хакен подготовили конфигурации графов, что заняло семьсот страниц рукописного текста, они загрузили их в компьютер и запрограммировали его на проверку многих тысяч частных случаев. Работу компьютера даже нельзя было проверить вручную. Вычисления заняли шесть месяцев, свыше тысячи часов машинного времени, и результатом стала гора распечаток высотой 1,2 м. Хотя люди в основном верят, что доказательство правильно, большинство чистых математиков находят его неэлегантным, неудовлетворительным и неспортивным. Все равно, как если бы Эвел Нивель похвастался, что пересечет Большой Каньон на мотоцикле, а потом построил мост и переехал по нему. Быть может, такие чувства испытывают настоящие альпинисты при виде людей, использующих бутылочки с кислородом во время высокогорного восхождения.