308
правок
Изменения
м
== Раскраска в 4 цвета ==
Нет описания правки
{{Теорема
|statement=
Пусть граф <tex>G</tex> - — планарный. Тогда <tex> \chi (G) \le 6</tex>
|proof=
Докажем по индукции.
{{Теорема
|statement=
Пусть граф <tex>G</tex> - — планарный. Тогда <tex> \chi (G) \le 5</tex>
|proof=
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
Обозначим за <tex> u </tex> - — возвращаемую вершину, <tex> v^{(k)} </tex> - — вершина, покрашенная в <tex> k </tex> цвет.
Если среди вершин, смежных <tex> u </tex>, есть две вершины одного цвета, значит остаётся один свободный цвет, в который мы и покрасим <tex> u </tex>.
Тогда попытаемся таким же образом перекрасить <tex> u </tex> в цвет 2, а смежную ей <tex>w_1^{(2)}</tex> в цвет 4 (со последующими перекрасками). Если удастся - раскраска получена.
Если нет, то получили ещё один цикл <tex> u w_1^{(2)} w_2^{(4)} w_3^{(2)} ... w_{k-1}^{(2)} w_k^{(4)} u </tex>. Но граф планарный, значит два полученных цикла пересекаются по крайней мере в двух вершинах - — <tex> u </tex> и какой-то другой, что невозможно, ведь вершины <tex> v_i </tex> первого цикла и <tex> w_j </tex> второго - — разных цветов. В этом случае получаем противоречие.
}}
Заметим что нельзя составить подобное доказательство для раскраски в 4 цвета, поскольку здесь наличие двух вершин одного цвета среди смежных <tex> u </tex> не исключает того, что все они раскрашены в разные цвета
== Источники ==
