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

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

Эта страница в последний раз была отредактирована 16 июня 2023 в 08:26.