Хотя сейчас мы приписываем постановку проблемы четырех красок Фрэнсису Гатри, во многих старых текстах эту честь отдают немецкому математику Августу Мёбиусу (1790–1868). Мёбиус, последователь Мартина Лютера, был тихим и замкнутым семьянином. Повзрослев, он редко путешествовал, но в бытность аспирантом посещал Лейпцигский университет, Гёттингенский университет (на протяжении двух семестров работал вместе с Гауссом), Университет в Галле, а затем вернулся в Лейпциг, где закончил работу над докторской диссертацией по астрономии. После этого периода частых переездов он предпочел остаться в своей любимой Саксонии. Несмотря на многократные предложения работы в других университетах, он сохранял верность Лейпцигу на протяжении всей оставшейся жизни.
В Лейпциге Мёбиус работал астрономом и стоял во главе тамошней обсерватории. Он любил математику и именно в математику, а не в астрономию, внес наиболее важный свой вклад. Больше всего он известен работами по барицентрическому исчислению, проективной и аффинной геометрии и основаниям топологии. Благодаря уединенному образу жизни и скрупулезному подходу к математике он создавал отличные работы, но это не делало его талантливым лектором. Поэтому на его занятия ходило очень мало платных студентов.
Ошибка атрибуции проистекает из истории, рассказанной одним из студентов Мёбиуса Ричардом Бальцером (1818–1887). Бальцер писал, что в 1840 г. Мёбиус поставил перед аудиторией проблему пяти принцев. Он описал ее следующим образом:
Однажды в Индии правил царь, у которого было большое царство и пять сыновей. В своем завещании он написал, что после его смерти царство должно быть поделено между сыновьями таким образом, чтобы территория каждого граничила (по линии, а не в одной точке) с территориями остальных четырех. Как было разделено царство116?
На следующий день Мёбиус признался студентам, что в таком виде задача неразрешима.
Рис. 14.3. Август Мёбиус
С учетом того, что нам известно, легко понять, почему у задачи нет решения. Предположим, что существует способ разделить царство на пять таких областей и что в каждой области имеется дворец принца. Тогда для любых двух братьев можно проложить дорогу между их дворцами, так что она не будет проходить по землям других братьев. Но это означает, что мы построили планарный граф, в котором вершинами являются дворцы, а ребрами — дороги. Точнее, это полный граф с пятью вершинами, K5, который, как мы доказали, планарным не является.
В постскриптуме Бальцер пришел к неверному выводу, будто неразрешимость этой задачи означает, что теорема о четырех красках верна. Он писал: «С каким восторгом Мёбиус, должно быть, видел далеко идущие применения» этой задачи117. Тонкая связь между проблемой пяти принцев и проблемой четырех красок заключается в том, что если бы нужное разделение царства существовало, то его карту (подобно карте на рис. 14.2) было бы невозможно раскрасить только лишь четырьмя цветами. Однако на самом деле это устраняет лишь одно препятствие к доказательству теоремы о четырех красках. Остается теоретическая возможность построить сложную карту, в которой нет пяти взаимно граничащих областей, но тем не менее раскрасить ее четырьмя цветами невозможно. По словам Мартина Гарднера, многие неправильные доказательства теоремы о четырех красках, ложившиеся в его почтовый ящик, на самом деле были не чем иным, как замаскированной проблемой пяти принцев.
Но не следует совсем отбрасывать задачку Мёбиуса. Метод соединения дворцов дорогами действительно полезен. Как и в задаче о кёнигсбергских мостах, точная география стран несущественна, важны лишь относительные местоположения. Это топологическая задача, которую можно переформулировать в терминах теории графов.
В графе смежности карты имеется по одной вершине для каждой страны, и две вершины соединены ребром, если у соответствующих стран есть общая граница (см. рис. 14.4). Если две страны граничат в нескольких местах, то мы все равно проводим между соответствующими вершинами только одно ребро. Нетрудно видеть, что граф смежности любой карты планарный. Просто будем считать, что вершины — это столицы стран, а ребра — дороги между столицами, проложенные внутри стран. По построению, в графе смежности нет ни петель, ни параллельных ребер; такой граф называется простым. Короче говоря, граф смежности карты является простым планарным графом. Заметим, что если карта связная, то таковым будет и граф смежности.