308
правок
Изменения
м
→Раскраска в 5 цветов
Пусть граф <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 5</tex>
|proof=
[[Файл:Planar chromatic number 1.png|230px|thumb|right|Нумерация двоичных чисел в прямом представленииu и смежные ей вершины]]
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
}}
{| cellpadding="10"
| '''Успешное перекрашивание''' ||
|-
| [[Файл:Planar chromatic number 2.png|280px]] || [[Файл:Planar chromatic number 3.png|280px]]
|}
{| cellpadding="10"
| '''Цикл 1-3''' ||
|-
| [[Файл:Planar chromatic number 4.png|280px]] || [[Файл:Planar chromatic number 5.png|280px]]
|}
Заметим что нельзя составить подобное доказательство для раскраски в 4 цвета, поскольку здесь наличие двух вершин одного цвета среди смежных <tex> u </tex> не исключает того, что все они раскрашены в разные цвета
