Действуя на основании ничем не подтвержденных предположений (это очень эффективный способ формирования рабочих идей, хотя в какой-то момент их все равно придется обосновать), считаем, что подобные препятствия всегда устранимы. Тогда получается, что любую карту можно раскрасить в четыре цвета, если известно, что некую меньшую карту можно так раскрасить. Может показаться, что такой вывод ничего нам не дает: как мы узнаем, что какую-то меньшую карту можно раскрасить нужным образом? Ответ в том, что эту же процедуру можно применить к меньшей карте, а затем к еще меньшей карте… и т. д. В конце концов, мы доберемся до карты настолько маленькой, что в ней будет всего четыре области, и это гарантирует, что ее можно раскрасить в четыре цвета. Теперь пройдем тот же путь в обратном направлении, на каждом шагу раскрашивая карту чуть побольше, чем в прошлый раз, и, в конце концов, доберемся до первоначальной карты.
Подобные рассуждения называют «доказательством по индукции». Это стандартный метод доказательства наиболее формализованных формулировок, и логику, на которой он основан, можно сделать строгой. Предложенная Кейли стратегия доказательства становится более понятной, если переформулировать ее с использованием логически эквивалентной концепции минимального контрпримера. В данном контексте контрпримером можно считать любую гипотетическую карту, которую невозможно раскрасить в четыре краски. Такая карта будет минимальной, если любую меньшую карту (т. е. карту с меньшим числом областей) можно раскрасить нужным образом. Если хотя бы один контрпример существует, то должен существовать и минимальный контрпример: чтобы его найти, нужно просто взять контрпример с минимальным возможным числом областей. Поэтому если минимального контрпримера не существует, то контрпримеров не существует вообще. А если их нет, то теорема о четырех красках верна.
Доказательство по индукции сводится примерно к следующему. Предположим, мы можем доказать, что минимальный контрпример всегда можно раскрасить в четыре краски, если можно раскрасить так некую связанную с ним меньшую карту. Тогда минимальный контрпример не может считаться собственно контрпримером. Поскольку эта карта минимальна, все меньшие карты можно раскрасить в четыре краски, поэтому, исходя из утверждения, которое, согласно принятому нами предположению, может быть доказано, то же верно в отношении первоначальной карты. Следовательно, минимального контрпримера не существует, а значит, не существует контрпримеров вообще. Эта идея сдвигает фокус проблемы, позволяя рассматривать не все карты сразу, а только гипотетические минимальные контрпримеры, и определяет процедуру редукции — способ последовательно вывести четырехкрасочность первоначальной карты из четырехкрасочности некой соответствующей меньшей карты.
Но зачем возиться с минимальными контрпримерами, не лучше ли поискать обычные? Это вопрос методики. Хотя первоначально мы не знаем, существуют ли контрпримеры, одно из парадоксальных, но очень полезных свойств этой стратегии заключается в том, что мы можем многое сказать о том, как должны выглядеть именно минимальные контрпримеры, если они существуют.
Для этого необходима способность рассуждать логически о гипотетических вещах — жизненно важное умение для любого математика. Чтобы дать вам почувствовать характер процесса, я докажу теорему о шести красках. Для этого мы позаимствуем прием из загадки о пяти принцах и переформулируем все в терминах двойственной сети, в которой области становятся точками. В этом случае задача о четырех красках эквивалентна другому вопросу: если на плоскости задана сеть, линии которой не пересекаются, можно ли раскрасить в четыре цвета точки так, чтобы две точки, соединенные линией, всегда были разного цвета? Точно так же можно переформулировать задачу с любым количеством красок.
Чтобы проиллюстрировать мощь метода минимальных контрпримеров, я докажу с их помощью, что любую плоскую сеть можно раскрасить в шесть цветов. Здесь главным нашим инструментом вновь станет формула Эйлера. Для точки плоской двойственной сети соседними точками назовем те, что соединены с ней линиями. У каждой точки может быть и множество соседей, и всего несколько. Можно показать, что, в соответствии с формулой Эйлера, у некоторых точек должно быть мало соседей. Точнее говоря, в плоской сети все точки не могут иметь по шесть и больше соседей. Доказательство этого момента я поместил в примечание, чтобы не прерывать ход мысли{18}. Этот факт дает нам рычаг, необходимый для того, чтобы разбить задачу на более мелкие подзадачи. Рассмотрим гипотетический минимальный контрпример для теоремы о шести красках. Это сеть, которую невозможно раскрасить в шесть разных цветов, притом что любую меньшую сеть так раскрасить можно. А теперь я доказываю, что такая карта не может существовать. Согласно приведенному выше следствию из формулы Эйлера, в ней должна быть хотя бы одна точка, у которой пять или меньше соседей. Временно уберем эту точку и линии, соединяющие ее с соседями. В получившейся сети меньше точек, поэтому, исходя из минимальности контрпримера, ее можно раскрасить в шесть цветов. (Этот шаг, кстати говоря, мы не сможем сделать, если наш контрпример будет не минимальным.) А теперь вернем удаленную точку и ее линии на место. Эта точка имеет не более пяти соседей, так что шестой цвет для нее всегда найдется. Покрасим ее — и получим успешно раскрашенный в шесть цветов минимальный контрпример; но тогда получается, что это никакой не контрпример. Значит, минимальных контрпримеров для теоремы о шести красках не существует, а значит, теорема верна.
Это внушает оптимизм. До сих пор, насколько нам известно, для раскраски некоторых карт могло потребоваться 20 цветов, или 703, или несколько миллионов. Теперь мы знаем, что такие карты не более реальны, чем горшок золота под концом радуги. Мы знаем, что конкретного ограниченного числа красок точно хватит на любую карту. Это настоящий триумф метода минимальных контрпримеров. Математики, посмотрев на него, взялись за дело с еще большим энтузиазмом, надеясь усилить аргументацию и постепенно заменить шесть красок на пять, а если повезет, и на четыре.
Юристы иногда тоже интересуются математическими задачами. Адвокат по имени Альфред Кемпе присутствовал на том заседании, где Кейли упомянул задачу о четырех красках. В свое время он под руководством Кейли изучал математику в Кембридже, и за годы его интерес к этой науке нисколько не ослаб. Не прошло и года после заседания, а Кемпе уже убедил себя, что ему удалось справиться с задачей. Свое решение он опубликовал в 1879 г. в недавно основанном журнале American Journal of Mathematics. Еще через год он опубликовал упрощенное доказательство, где были исправлены некоторые ошибки, присутствовавшие в первом. Вот как он подошел к вопросу: «Очень небольшое изменение в части карты может привести к необходимости перекрашивать ее целиком. В результате достаточно сложного поиска мне удалось отыскать слабое звено, которое позволило одержать победу».
Я изложу идеи Кемпе в терминах двойственной сети. Опять же он начал с формулы Эйлера и следующего из нее вывода о существовании точки с тремя, четырьмя или пятью соседями. (Точка с двумя соседями лежит на линии и никак не влияет на структуру сети или карты: на нее можно просто не обращать внимания.)
Если существует точка с тремя соседями, то процедуру, которую я использовал для доказательства теоремы о шести красках, можно применить и к четырехкрасочному варианту. Удаляем саму точку и линии, которые в ней сходятся, раскрашиваем в четыре краски результат, возвращаем точку и линии на место и окрашиваем ее в оставшийся свободным цвет. Поэтому мы можем считать, что точки с тремя соседями не существует.
Если существует точка с четырьмя соседями, то вышеописанная методика не срабатывает, потому что при возвращении точки свободного цвета может и не оказаться. Кемпе придумал хитрый способ обойти это препятствие: он предложил так же точно удалить точку, но после этого поменять расцветку получившейся меньшей карты так, чтобы два из четырех ее бывших соседей получили один и тот же цвет. После такой модификации у соседей удаленной точки окажется не больше трех цветов — и в нашем распоряжении окажется свободный четвертый. Основная идея перекраски схемы по Кемпе заключается в том, что две соседние точки должны быть разных цветов — скажем, синего и красного, а еще в схеме используются зеленый и желтый. Если обе оставшиеся точки окажутся зелеными или желтыми, то второй цвет окажется свободным и может быть использован для удаленной точки. Исходя из этого, считаем, что одна из них зеленая, а вторая — желтая. Теперь найдем все точки, которые соединены с синей точкой последовательностью линий, проходящих только через синие и красные точки, и назовем их красно-синей цепочкой Кемпе{19}. По определению, любой сосед любой точки в цепочке Кемпе, не принадлежащий цепочке, должен быть зеленым или желтым, поскольку синий или красный сосед там уже есть. Обратите внимание, что замена цветов в пределах цепочки Кемпе (синий на красный, и наоборот) дает новый вариант карты, в которой по-прежнему выполняется ключевое условие о том, что соседние точки должны быть разных цветов (см. рис. 11).
Если красный сосед нашей точки не является частью выделенной сине-красной цепочки, проведите такую замену. Синий сосед точки сделается красным, а красный останется красным по-прежнему. Теперь соседи нашей точки окрашены не более чем в три цвета: красный, зеленый и желтый, что позволяет нам окрасить точку в синий цвет — и дело сделано. Однако сине-красная цепочка может описать петлю и замкнуться на синем соседе нашей точки. Если так, оставьте в покое синий и красный цвета и проделайте ту же операцию с ее желтыми и зелеными соседями. Начните с зеленой точки и сформируйте желто-зеленую цепочку Кемпе. Заметьт