Изменения
Нет описания правки
{{Теорема
|statement=
Пусть граф <tex>G</tex> - — планарный. Тогда <tex> \chi (G) \le 6.</tex>
|proof=
Докажем по индукции.
{{Теорема
|statement=
Пусть граф <tex>G</tex> - — планарный. Тогда <tex> \chi (G) \le 5.</tex>
|proof=
[[Файл:Planar chromatic number 1.png|230px|thumb|right|u и смежные ей вершины]]
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
Обозначим за <tex> u </tex> - — возвращаемую вершину, <tex> v^{(k)} </tex> - — вершину, покрашенную в <tex> k </tex> цвет.
Если среди вершин, смежных <tex> u </tex>, есть две вершины одного цвета, значит остаётся по меньшей мере один свободный цвет, в который мы и покрасим <tex> u </tex>.
Если же в соответствии со 2-ым вариантом перекраска не удалась, это означает, что в графе есть цикл <tex> u v_1^{(1)} v_2^{(3)} v_3^{(1)} ... v_{k-1}^{(1)} v_k^{(3)} 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> второго - — разных цветов. Значит такой случай наступить не мог.
}}
{| cellpadding="10"
| || || || || Успешное перекрашивание || || || || || || Цикл 1-31—3, перекрасить не удаётся ||
|-
| || || || || [[Файл:Planar chromatic number 2.png|264px]] || || || || || || [[Файл:Planar chromatic number 34.png|264px228px]] |-| || || || || [[Файл:Planar chromatic number 43.png|228px264px]] || || || || || || [[Файл:Planar chromatic number 5.png|228px]]
|}
