Теорема о пяти красках для планарных карт

Введение

Плоскостные карты требуют не более пяти цветов.

Теорема о пяти цветах — это результат из теории графов, утверждающий, что если плоскость разделена на области, например, как политическая карта стран мира, то эти области можно раскрасить, используя не более пяти цветов, так, чтобы никакие две соседние области не были окрашены в один и тот же цвет. Теорема о пяти цветах вытекает из более строгой теоремы о четырех цветах, но её значительно легче доказать. Она была основана на неудачной попытке доказать теорему о четырех цветах, предпринятой Альфредом Кемпе в 1879 году. Перси Джон Хьювуд обнаружил ошибку спустя 11 лет и доказал теорему о пяти цветах, опираясь на работу Кемпе.

Очертание доказательства противоречия

Прежде всего, данной карте сопоставляется простой планарный граф, а именно, в каждой области карты помещается вершина, затем две вершины соединяются ребром, если и только если соответствующие области имеют общую границу. Затем задача сводится к задаче раскраски графа: необходимо раскрасить вершины графа так, чтобы ни одно ребро не имело конечных точек одного цвета. Поскольку это простой планарный граф, то есть он может быть вложен в плоскость без пересекающихся ребер, и у него нет двух вершин, соединенных более чем одним ребром, и у него нет петель, то можно показать (используя характеристику Эйлера плоскости), что у него должна быть вершина, смежная не более чем с пятью ребрами. (Примечание: это единственное место в доказательстве, где используется условие о пяти цветах. Если этот метод используется для доказательства теоремы о четырех цветах, он потерпит неудачу на этом шаге. Фактически, икосаэдрический граф является 5-регулярным и планарным и, следовательно, не имеет вершины, смежной не более чем с четырьмя ребрами.) Найдите такую вершину и назовите ее .
Теперь удалите из графа . Полученный граф имеет на одну вершину меньше, чем , поэтому по индукции можно предположить, что его можно раскрасить только пятью цветами. Если при раскраске не использованы все пять цветов на пяти соседних вершинах , его можно раскрасить в цвет, не используемый соседями. Теперь рассмотрим эти пять вершин , , , , которые смежны с в циклическом порядке (который зависит от того, как записан G). Итак, можно предположить, что , , , , раскрашены цветами 1, 2, 3, 4, 5 соответственно. Теперь рассмотрим подграф графа , состоящий из вершин, раскрашенных только цветами 1 и 3, и ребер, соединяющих их. Для ясности, каждое ребро соединяет вершину цвета 1 с вершиной цвета 3 (это называется цепью Кемпе). Если и лежат в разных связных компонентах , мы можем поменять цвета 1 и 3 на компоненте, содержащем , не затрагивая раскраску остальной части графа. Это освобождает цвет 1 для , завершая задачу. Если же и лежат в одной связной компоненте , мы можем найти путь в , соединяющий их, состоящий только из вершин цветов 1 и 3. Теперь обратимся к подграфу графа , состоящему из вершин, раскрашенных только цветами 2 и 4, и ребер, соединяющих их, и применим те же аргументы, что и раньше. Тогда либо мы сможем изменить раскраску 2-4 на подграфе , содержащем , и раскрасить в цвет 2, либо мы сможем соединить и путем, состоящим только из вершин цветов 2 и 4. Такой путь пересечет 1-3 окрашенный путь, который мы построили ранее, поскольку , , , были расположены в циклическом порядке. Это явно абсурдно, поскольку противоречит планарности графа. Следовательно, можно раскрасить в пять цветов, вопреки первоначальному предположению.

First of all, one associates a simple planar graph to the given map, namely one puts a vertex in each region of the map, then connects two vertices with an edge if and only if the corresponding regions share a common border. The problem is then translated into a graph coloring problem: one has to paint the vertices of the graph so that no edge has endpoints of the same color. Because is a simple planar, i. e. it may be embedded in the plane without intersecting edges, and it does not have two vertices sharing more than one edge, and it does not have loops, then it can be shown (using the Euler characteristic of the plane) that it must have a vertex shared by at most five edges. (Note: This is the only place where the five color condition is used in the proof. If this technique is used to prove the four color theorem, it will fail on this step. In fact, an icosahedral graph is 5 regular and planar, and thus does not have a vertex shared by at most four edges.) Find such a vertex, and call it
Now remove from The graph obtained this way has one fewer vertex than , so we can assume by induction that it can be colored with only five colors. If the coloring did not use all five colors on the five neighboring vertices of , it can be colored in with a color not used by the neighbors. So now look at those five vertices , , , , that were adjacent to in cyclic order (which depends on how we write G). So we can assume that , , , , are colored with colors 1, 2, 3, 4, 5 respectively. Now consider the subgraph of consisting of the vertices that are colored with colors 1 and 3 only and the edges connecting them. To be clear, each edge connects a color 1 vertex to a color 3 vertex (this is called a Kempe chain). If and lie in different connected components of , we can swap the 1 and 3 colors on the component containing without affecting the coloring of the rest of This frees color 1 for completing the task. If on the contrary and lie in the same connected component of , we can find a path in joining them that consists of only color 1 and 3 vertices. Now turn to the subgraph of consisting of the vertices that are colored with colors 2 and 4 only and the edges connecting them, and apply the same arguments as before. Then either we are able to reverse the 2 4 coloration on the subgraph of containing and paint color 2, or we can connect and with a path that consists of only color 2 and 4 vertices. Such a path would intersect the 1 3 colored path we constructed before since through were in cyclic order. This is clearly absurd as it contradicts the planarity of the graph. So can in fact be five colored, contrary to the initial presumption.

Альтернативное доказательство

Кайнен (1974) приводит упрощенное доказательство теоремы о пяти раскрасках, основанное на непланарности K6 (полного графа с 6 вершинами) и минорах графов. Это доказательство обобщается на графы, которые можно сделать планарными удалением двух ребер.