Теорема о пяти красках

Перейти к навигацииПерейти к поиску
Пример 5-цветной карты.
Примечание: Данную карту можно раскрасить в 4 цвета

Теорема о пяти красках — ослабленный вариант теоремы о четырёх красках: вершины любого планарного графа можно покрасить в пять цветов так, чтобы любые две смежные вершины были разных цветов (данный способ покраски в математике называют правильным), или, что то же самое, хроматическое число планарного графа не больше 5. Теорема была доказана Перси Хивудом в 1890 году, его доказательство основано на исправлении ошибки в неудачной попытке доказательства Альфреда Кемпе[англ.] предпринятой в 1879 году, которое считалось обоснованным в течение 11 лет.

Доказательство

В отличие от теоремы о четырёх красках, доказательство является достаточно компактным. Ведётся индукцией по количеству вершин графа. В базе индукции факт, что при можно просто покрасить вершины в различные цвета.

Для индуктивного перехода показывается, что если для графа из вершины все планарные графы с вершинами можно правильно покрасить в 5 цветов, то и сам граф может быть покрашен в пять цветов. Для этого используется следствие из формулы Эйлера о том, что в планарном графе найдётся вершина степени меньше . Поскольку граф раскрашивается в цветов правильным образом, то возможны два варианта: 1) если степень менее или какие-то две соседние вершины покрашены в один цвет (в этом случае найдётся цвет, в который не покрашена ни одна из соседних вершин , а тогда можно покрасить в этот цвет, и покраска будет правильной) 2) степень вершины равна и все смежные с ней вершины раскрашены в разные цвета.

Для второго варианта пять смежных с вершин нумеруются в порядке обхода соответствующих исходящих рёбер по часовой стрелке: ; за обозначается цвет вершины ; определяется подграф графа без как подграф, содержащий все вершины, окрашенные в цвета вершин и . Далее рассматривается два случая:

1. Вершины и лежат в разных компонентах связности графа . В этом случае возможно перекрасить вершины из той же компоненты, что и , следующим образом: перекрашиваем все вершины цвета в цвет , а все вершины цвета в цвет . Покраска графа без по-прежнему останется правильной, но при этом теперь вершина будет покрашена в цвет , а не , а значит можно покрасить вершину в цвет и получить требуемую раскраску графа .

2. Вершины и лежат в одной компоненте связности графа . Тогда между вершинами и существует путь в графе . Вместе с вершиной и рёбрами и данный путь образует цикл . Так как граф планарен, а  — несамопересекающийся цикл, то по теореме Жордана делит плоскость на компоненты связности (внешняя и внутренняя), причём точки и будут находиться в разных компонентах, а следовательно, не существует пути из в в графе . Тогда и находятся в разных компонентах связности графа , и можно аналогично рассуждениям из случая 1 перекрасить вершины из той же компоненты связности графа , что и , следующим образом: перекрашиваются все вершины цвета в цвет , а все вершины цвета в цвет , а затем покрасить вершину в цвет и получить требуемую раскраску графа .