* Переход
Предположим, что для планарного графа с <tex>N</tex> вершинами существует раскраска в 6 цветов. Докажем то же для графа с <tex> N+1 </tex> вершиной.
По только что доказанной лемме в <tex> G </tex> найдётся вершина степени не больше 5. Удалим её; по предположению индукции получившийся граф можно раскрасить в 6 цветов.
{{Теорема
|statement=
Пусть граф <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 65</tex>
|proof=
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе на шаге 3. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
Обозначим за <tex> u </tex> - возвращаемую вершину, <tex> v^{(k)} </tex> - вершина, покрашенная в <tex> k </tex> цвет.
Если среди вершин, смежных <tex> u </tex> , есть две вершины одного цвета, значит остаётся один свободный цвет, в который мы и покрасим <tex> u </tex>. Иначе, уложим полученный после удаления <tex> u </tex> граф на плоскость и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.
ИначеПопробуем покрасить <tex> u </tex> в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину <tex>v_1^{(1)}</tex> в цвет 3. Если среди смежных ей вершин есть вершины <tex> v_2^{(3)} </tex>, покрасим их в цвет 1, уложим полученный после шага и так далее. Рассмотрим 2 граф на плоскость необычных варианта, которые могут наступить во время обхода:#мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме 1 <tex>\leftrightarrow</tex> 3, и пронумеруем если мы получили две смежные вершины одного цвета , значит и до перекрасок в порядке обхода смежных вершин графе были две вершины одинакового цвета, а по часовой стрелкепредположению граф без <tex> u </tex> был раскрашен правильно.#дойдём до вершины, смежной <tex> u </tex>, исходно имевшей цвет 3, которую перекрасить в 1 нельзя (<tex> u </tex> теперь имеет цвет 1).
Попробуем покрасить Если этот процесс был успешно завершён, то получили правильную раскраску.Если же в соответствии со 2-ым вариантом перекраска не удалась, это означает, что в <tex> u G </tex> в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину есть цикл <tex>u v_1^{(1)}</tex> в цвет 3. Если среди смежных ей вершин есть вершины <tex> v_2 </tex> цвета ^{(3, покрасим их в цвет )} v_3^{(1, и так далее)} . Если этот процесс прекратится, то требуемая раскраска получена. В противном случае могут наступить 2 варианта: #мы дойдём до уже однажды перекрашенной вершины (возможно не однажды). В таком случае раскраска останется правильной, поскольку мы меняли цвета вершин по схеме v_{k-1 <tex>\leftrightarrow</tex> 3, и неправильность полученной раскраски означала бы неправильность исходной. #дойдём до вершины, смежной <tex> u </tex>, исходно имевшей цвет 3, которую перекрасить в }^{(1 нельзя )} v_k^{(<tex> 3)} u </tex> уже перекрашена в цвет 1).
Если Тогда попытаемся таким же образом перекрасить <tex> u </tex> в соответствии со цвет 2-ым вариантом перекраска не удалась, это означает, что есть цикл а смежную ей <tex> u v_1w_1^{(12)} v_2^{</tex> в цвет 4 (3)} v_3^{(1со последующими перекрасками)} ... v_{kЕсли удастся -1}^{(1)} v_k^{(3)} u </tex>раскраска получена.
Таким же образом попытаемся перекрасить Если нет, то получили ещё один цикл <tex> u w_1^{(2)} w_2^{(4)} w_3^{(2)} ... w_{k-1}^{(2)} w_k^{(4)} u </tex> . Но граф планарный, значит два полученных цикла пересекаются по крайней мере в цвет 2двух вершинах - <tex> u </tex> и какой-то другой, что невозможно, а смежную ей ведь вершины <tex>w_1^{(2)}v_i </tex> первого цикла и <tex> w_j </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> не учитываем) - противоречие
}}
Заметим что нельзя составить подобное доказательство для раскраски в 4 цвета, поскольку здесь наличие двух вершин одного цвета среди смежных <tex> u </tex> не исключает того, что все они раскрашены в разные цвета
== Раскраска в 4 цвета ==
