Условие

Граф - это набор вершин, причем некоторые из них соединены ребрами (каждое ребро соединяет ровно две вершины графа). Раскраска вершин графа называется правильной, если вершины одного цвета не соединены ребром. Некоторый граф правильно раскрашен в k цветов, причем его нельзя правильно раскрасить в меньшее число цветов.

Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех k цветов ровно по одному разу.


Показать решение