Изменения
→Раскраска в 5 цветов
|proof=
[[Файл:Planar chromatic number 1.png|230px|thumb|right|u и смежные ей вершины]]
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с <tex>5</tex>-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
Обозначим за <tex> u </tex> — возвращаемую вершину, <tex> v^{(k)} </tex> — вершину, покрашенную в <tex> k </tex> цвет.
Иначе, уложим полученный после удаления <tex> u </tex> граф на плоскость, вернём вершину <tex> u </tex> (пока бесцветную) и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.
Попробуем покрасить <tex> u </tex> в цвет <tex>1</tex>. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину <tex>v_1^{(1)}</tex> в цвет <tex>3</tex>. Если среди смежных ей вершин есть вершины <tex> v_i^{(3)} </tex>, покрасим их в цвет <tex>1</tex>, и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода:
#мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно, что не получится сделать). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме <tex>1</tex> <tex>\leftrightarrow</tex> <tex>3</tex>, и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в этом месте были две вершины одинакового цвета, а по предположению граф без <tex> u </tex> был раскрашен правильно.
#дойдём до вершины, смежной <tex> u </tex>, исходно имевшей цвет <tex>3</tex>, которую перекрасить в <tex>1 </tex> нельзя (<tex> u </tex> теперь имеет цвет <tex>1</tex>).
Если этот процесс был успешно завершён, то получили правильную раскраску.
Если же в соответствии со 2-ым вторым вариантом перекраска не удалась, это означает, что в графе есть цикл <tex> u v_1^{(1)} v_2^{(3)} v_3^{(1)} \ldots v_{k-1}^{(1)} v_k^{(3)} u </tex>.
Тогда попытаемся таким же образом перекрасить <tex> u </tex> в цвет <tex>2</tex>, а смежную ей <tex>w_1^{(2)}</tex> в цвет <tex>4 </tex> (со последующими перекрасками). Если удастся — раскраска получена.
Если нет, то получили ещё один цикл <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> не исключает того, что при их (смежных вершин) раскраске использовались все возможные цвета.
== Раскраска в 4 цвета ==
