Раскрашивание планарных графов. Теорема о пяти красках. Теорема о четырех красках


Теорема (о пяти красках, Теорема Хивуда): Всякий связный планарный граф 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 вершины v1, v2,…,v4 получат в G’ не более 4-х красок. Вершину v можно раскрасить любой из оставшейся красок.

2) Deg(v) = 5. Если смежные с v вершины v1, v2,…,v5 имеют в совокупности r ≤ 4 красок, то вершину v можно раскрасить в оставшийся цвет. Пусть теперь вершины v1, v2,…,v5 окрашены в 5 цветов C1, C2,…,C5 соответственно. Натянем на вершины v1, v2,…,v5 из G подграф H, соединив v1, v2,…,v5 в H ребрами так, как они соединены в G. Подграф H – планарный ⇒ H не содержит K5, значит в H среди вершин v1, v2,…,v5 существуют две несмежные вершины, ибо если все вершины v1, v2,…,v5 смежны, то граф H содержит K5, чего нет. Пусть для определенности вершины v1,v2 не смежны. Склеим v1, v2 с вершиной v. Полученный связный граф по предположению индукции 5-раскрашиваем. При этом 4 вершины v, v3, v5 получат: r ≤ 4 краски.

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

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


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




Статистика