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

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

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

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

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

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

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