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