|
|
 |
Условие
Раскраска вершин графа называется правильной, если вершины одного цвета не соединены ребром. Некоторый граф правильно раскрашен в k цветов, причём его нельзя правильно раскрасить в меньшее число цветов. Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех k цветов ровно по одному разу.
Решение
Цвета, в которые покрашен граф, занумеруем от 1 до k. Те вершины цвета 2, которые не соседствуют ни с какими вершинами цвета 1, перекрасим в цвет 1. Новая раскраска будет правильной, поэтому в ней k цветов. Значит, какие-то вершины цвета 2 не перекрашены и потому соседствуют с вершинами цвета 1. Аналогично, вершины цвета 3, которые не соседствуют с вершинами цвета 2,
перекрасим в цвет 2, и т. д. вплоть до последнего цвета.
После этого рассмотрим какую-либо вершину цвета k. Она не перекрашена, и потому соседствует с вершиной цвета k – 1. Эта вершина тоже не перекрашена, так как иначе её первоначальный цвет был бы k, и она не могла бы соседствовать с вершиной того же цвета. Раз вершина не перекрашена, то она соседствует с вершиной цвета k – 2, и т. д. Продолжая этот процесс, построим путь из вершин k
цветов, которые не были перекрашены.
