Олимпиадные задачи из источника «1999 год» для 11 класса - сложность 3 с решениями
Раскраска вершин графа называется <i>правильной</i>, если вершины одного цвета не соединены ребром. Некоторый граф правильно раскрашен в <i>k</i> цветов, причём его нельзя правильно раскрасить в меньшее число цветов. Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех <i>k</i> цветов ровно по одному разу.