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

Хотя не известно, все ли планарные графы 4-раскрашиваемы, все они, несомненно, 5-раскрашиваемы. Мы приведем доказательство этого известного утверждения, принадлежащее Хивуду.

Теорема.Каждый планарный граф 5-раскрашиваем.

Доказательство. Будем доказывать индукцией по числу р вершин. Для любого планарного графа с р<5 вершинами результат тривиален, поскольку такой граф р-раскрашиваем.

Допустим, что все планарные графы с р вершинами (р>= 5) 5-раскрашиваемы. Пусть G — плоский граф с р+1 вершинами. В силу следствия в графе G найдется вершина v степени 5 или менее. По предположению индукции плоский граф G - v 5-раскрашиваем.

Рассмотрим приписывание цветов вершинам графа G — v, при котором получается 5-раскраска; цвета будем обозначать через ci, l<ci<5. Ясно, что если некоторый цвет, скажемcj, не используется в раскраске вершин, смежных сu, то, приписав цвет сj вершине v, получим 5-раскраску графа G.

Осталось рассмотреть случай, когда deg v = 5 и для вершин графа G, смежных с v, используются все пять цветов. Переставим номера цветов, если это необходимо, так, чтобы вершины, смежные с v и окрашенные в цвета c1, с2, с3, с4, с5, были циклически упорядочены. Пометим теперь вершину, смежную с v окрашенную цветом ci, буквой vi, l<i<5

Обозначим через G13 подграф графа G — v, порожденный всеми вершинами, окрашенными в один из цветов с1 и с3. Если вершины v1 и v3 принадлежат различным компонентам графа G13, то 5-раскраску графа G - v можно получить, поменяв друг с другом (c1 на с3 и обратно)

цвета вершин той компоненты графа G13, которая содержит их. В этой 5-раскраске уже нет вершин, смежных с v и окрашенных в цветc1; поэтому, окрасив v в цвет с1, образуем 5-раскраску графа G. Если же вершины v1 и v3 принадлежат одной и той же компоненте графа G13, то в G между v1 и v3 существует простая цепь, все вершины которой окрашены в цвета с1 и с3. Эта цепь вместе с цепью v1v3 образует простой цикл, который обязательно окружает или вершину v2, или вершины v4 и у5. В любом из этих случаев v2 и v4 нельзя соединить простой цепью, все вершины которой окрашены в цвета с2 и с4. Следовательно, рассматривая подграф G24 графа G - v, порожденный всеми вершинами, окрашенными в цвета с2 и с4, заключаем, что вершины v2 и v4 принадлежат различным его компонентам. Таким образом, если поменять между собой цвета вершин в компоненте подграфа G24, содержащей v2, получим 5-раскраску графа G - v, и в ней ни одна из вершин, смежных с v, не будет окрашена в цвет с2. Поэтому, окрасив вершину v в цвет с2, образуем 5-раскраску всего графа G.