Приложение

*1. Проблема пяти красок

Доказательство того, что всякая карта на сфере может быть правильно раскрашена с помощью не более чем пяти различных красок, основывается на формуле Эйлера. (В соответствии с тем, что было сказано на стр. 277, карта считается раскрашенной правильно, если никакие две области, соприкасающиеся по целой дуге, не окрашены одинаково.) Мы ограничимся рассмотрением таких карт, на которых все области "являются простыми замкнутыми многоугольниками, ограниченными круговыми дугами. Не уменьшая общности, можно допустить, что в каждой вершине сходится ровно по три дуги; карту, удовлетворяющую такому условию, будем называть регулярной. Заменим каждую вершину, в которой встречается более трех дуг, маленьким кружком и присоединим внутренность этого кружка к одной из прилегающих областей: тогда получится новая карта, в которой "кратные" вершины заменены обыкновенными. Новая карта будет содержать столько же областей, сколько и старая, и будет регулярной. Если ее удастся правильно раскрасить, то, сжимая потом кружок и сводя его в точку, мы получим требуемую раскраску первоначальной карты. Таким образом, достаточно убедиться, что каждую регулярную карту на сфере можно правильно раскрасить пятью красками.

Прежде всего докажем, что всякая регулярная карта содержит по крайней мере один многоугольник с числом сторон, меньшим шести. Обозначим через Fn число я-угольных областей нашей регулярной карты; тогда, обозначая через F число всех областей, получим равенство

У каждой дуги - два конца; в каждой вершине сходится три дуги. Поэтому если Е обозначает число дуг, а V - число вершин на нашей карте, то

Далее, так как область, ограниченная n дугами, имеет n вершин и каждая вершина принадлежит трем областям, то

По формуле Эйлера, мы имеем:

Из соотношения (2) следует, что 6V = 4E, так что 6F - 2Е = 12. Тогда соотношения (1) и (3) нам дают

или

Так как хотя бы один из членов суммы слева должен быть положительным, то отсюда ясно, что четыре числа F₂, F₃, F₄ и F₅ не могут одновременно равняться нулю. Но это и есть то, что нам нужно было доказать.

Перейдем теперь к теореме о пяти красках. Пусть М - какая угодно регулярная карта на сфере, n - число всех ее областей. Мы знаем, что имеется хоть одна область с числом сторон, меньшим шести.

Случай 1. М содержит область A с 2, 3 или 4 сторонами (рис. 146). В этом случае удалим дугу, отделяющую А от одной из прилежащих областей. (Здесь необходимо следующее примечание. Если у области А четыре стороны, то может случиться, что одна из прилежащих областей, если ее обойти вокруг, окажется также прилежащей к A с противоположной стороны. В этом случае, на основании теоремы Жор дана, две области, прилегающие к А с двух остальных сторон, будут различными, и мы сможем удалить одну из этих двух сторон.) Вновь полученная карта М' будет также регулярной, но содержащей уже только n-1 областей. Если карту М' можно правильно раскрасить пятью красками, то можно раскрасить и карту М. В самом деле, к области А прилегает самое большее четыре области карты М, и потому для А всегда найдется пятая краска.

Рис. 146-147. К доказательству теоремы о пяти красках

Случай 2. М содержит область A с пятью сторонами. Рассматривая ( пять областей, прилегающих к A, обозначим их через В, С, D, Е и F. Можно всегда среди этих пяти областей найти две, которые не прилегают друг к другу: действительно, если, например, В и D прилегают одна к другой, то отсюда вытекает, что С не прилегает ни к E, ни к F, так как в противном случае всякий путь, идущий из С в E или F, должен был бы пройти по крайней мере через одну из областей A, В или D (рис. 147). (Ясно, что это утверждение существенно зависит от теоремы Жордана, справедливой для плоскости и для сферы. Для тора, напротив, все это рассуждение отпадает.) Итак, можно допустить, что, например, С и F не прилегают друг к другу. Удалим те две стороны A, которые отделяют A от С и F, и тогда получим новую карту М' с n-2 областями, также регулярную. Если новую карту М' можно правильно раскрасить пятью красками, то можно раскрасить и первоначальную карту М. В самом деле, после восстановления удаленных сторон область A будет прилегать к пяти областям, окрашенным не более чем четырьмя красками (так, как С и F окрашены одинаково); и потому для A всегда найдется пятая краска.

Таким образом, во всех случаях всякой регулярной карте M с n областями можно сопоставить такую, также регулярную карту М' с n-1 или n-2 областями, что если М' можно раскрасить пятью красками, то М - также. Это рассуждение можно повторить для карты М' и т. д. В результате мы получим последовательность карт, первым членом которой является М:

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

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