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

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

Теорема о пяти красках — ослабленный вариант теоремы о четырёх красках: вершины любого планарного графа можно покрасить в пять цветов так, чтобы любые две смежные вершины были разных цветов (данный способ покраски в математике называют правильным), или, что то же самое, хроматическое число планарного графа не больше 5. Теорема была доказана Перси Хивудом в 1890 году, его доказательство основано на исправлении ошибки в неудачной попытке доказательства Шаблон:Iw предпринятой в 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$.