Изменения
→Раскраска в 5 цветов
Если среди вершин, смежных <tex> u </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, и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода:
