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

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

ДоказательствоПравить

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

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

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

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

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