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

---

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

---