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

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

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

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

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

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

Для второго варианта пять смежных с $u$ вершин нумеруются в порядке обхода соответствующих исходящих рёбер по часовой стрелке: $v_{1},v_{2},v_{3},v_{4},v_{5}$; за $c_{i}$ обозначается цвет вершины $v_{i}$; определяется подграф $H_{ij}$ графа $G$ без $u$ как подграф, содержащий все вершины, окрашенные в цвета вершин $v_{i}$ и $v_{j}$. Далее рассматривается два случая:

1. Вершины $v_{1}$ и $v_{3}$ лежат в разных компонентах связности графа $H_{13}$. В этом случае возможно перекрасить вершины из той же компоненты, что и $v_{1}$, следующим образом: перекрашиваем все вершины цвета $c_{1}$ в цвет $c_{3}$, а все вершины цвета $c_{3}$ в цвет $c_{1}$. Покраска графа $G$ без $u$ по-прежнему останется правильной, но при этом теперь вершина $v_{1}$ будет покрашена в цвет $c_{3}$, а не $c_{1}$, а значит можно покрасить вершину $u$ в цвет $c_{1}$ и получить требуемую раскраску графа $G$.

2. Вершины $v_{1}$ и $v_{3}$ лежат в одной компоненте связности графа $H_{13}$. Тогда между вершинами $v_{1}$ и $v_{3}$ существует путь в графе $H_{13}$. Вместе с вершиной $u$ и рёбрами $(v_{3},u)$ и $(u,v_{1})$ данный путь образует цикл $C_{13}$. Так как граф $G$ планарен, а $C_{13}$ — несамопересекающийся цикл, то по теореме Жордана $C_{13}$ делит плоскость на $2$ компоненты связности (внешняя и внутренняя), причём точки $v_{2}$ и $v_{4}$ будут находиться в разных компонентах, а следовательно, не существует пути из $v_{2}$ в $v_{4}$ в графе $H_{24}$. Тогда $v_{2}$ и $v_{4}$ находятся в разных компонентах связности графа $H_{24}$, и можно аналогично рассуждениям из случая 1 перекрасить вершины из той же компоненты связности графа $H_{24}$, что и $v_{2}$, следующим образом: перекрашиваются все вершины цвета $c_{2}$ в цвет $c_{4}$, а все вершины цвета $c_{4}$ в цвет $c_{2}$, а затем покрасить вершину $u$ в цвет $c_{2}$ и получить требуемую раскраску графа $G$.