Теорема (о пяти красках, Теорема Хивуда): Всякий связный планарный граф G можно правильно раскрасить не более чем 5-ю красками.

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

Предположение индукции: Допустим, что любой связный планарный граф с числом вершин k < p 5-раскрашиваем. Шаг индукции: Покажем, что любой связный граф планарный граф с p вершинами 5-раскрашиваем. Т.к. граф G связен и планарен, то он имеет вершину v степени S ≤ 5. Удалим из G вершину V вместе с инцидентными ей ребрами. Полученный планарный граф G’=G-v имеет число вершин k < p и потому по предположении индукции все компоненты связности графа G’ можно раскрасить не более чем 5-ю цветами. Возможны следующие случаи: 1) степень вершины v не более 4. Пусть для определенности deg(v)=4. Смежные с v вершины v₁, v₂,…,v₄ получат в G’ не более 4-х красок. Вершину v можно раскрасить любой из оставшейся красок.

2) Deg(v) = 5. Если смежные с v вершины v₁, v₂,…,v₅ имеют в совокупности r ≤ 4 красок, то вершину v можно раскрасить в оставшийся цвет. Пусть теперь вершины v₁, v₂,…,v₅ окрашены в 5 цветов C₁, C₂,…,C₅ соответственно. Натянем на вершины v₁, v₂,…,v₅ из G подграф H, соединив v₁, v₂,…,v₅ в H ребрами так, как они соединены в G. Подграф H – планарный ⇒ H не содержит K₅, значит в H среди вершин v₁, v₂,…,v₅ существуют две несмежные вершины, ибо если все вершины v₁, v₂,…,v₅ смежны, то граф H содержит K₅, чего нет. Пусть для определенности вершины v₁,v₂ не смежны. Склеим v₁, v₂ с вершиной v. Полученный связный граф по предположению индукции 5-раскрашиваем. При этом 4 вершины v, v₃, v₅ получат: r ≤ 4 краски.

Расклеим назад v₁, v₂, v. Вершины v₁, v₂ оставим их прежний цвет (как у v). Тогда вершины v₁, v₂,…,v₅ [v₁, v₂ – одинаково раскрашены] имеют r ≤ 4 цвета. Вершину v перекрасим в один из оставшихся цветов. Шаг индукции установлен. Теорема доказана.

Замечание: Широко известна проблема четырех красок: любой плоский граф 4-раскрашиваем. Появилось много ошибочных доказательств. Последнее сообщение о доказательстве теоремы вышло в 1977 году на ≈ 180 листах (!!!).

Комментарии запрещены.