Изменения
→Раскраска в 5 цветов
Попробуем покрасить <tex> u </tex> в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину <tex>v_1^{(1)}</tex> в цвет 3. Если среди смежных ей вершин есть вершины <tex> v_i^{(3)} </tex>, покрасим их в цвет 1, и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода:
#мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно, что не получится сделать). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме <tex>1 </tex> <tex>\leftrightarrow</tex> <tex> 3</tex>, и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в этом месте были две вершины одинакового цвета, а по предположению граф без <tex> u </tex> был раскрашен правильно.
#дойдём до вершины, смежной <tex> u </tex>, исходно имевшей цвет 3, которую перекрасить в 1 нельзя (<tex> u </tex> теперь имеет цвет 1).
