Разделы 
Дополнительно
Задача по математике - 3309
2019-06-02 
Граф - это набор вершин, причем некоторые из них соединены ребрами (каждое ребро соединяет ровно две вершины графа). Раскраска вершин графа называется правильной, если вершины одного цвета не соединены ребром. Некоторый граф правильно раскрашен в $k$ цветов, причем его нельзя правильно раскрасить в меньшее число цветов. Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех $k$ цветов ровно по одному разу.
Решение:
Цвета, в которые покрашен граф, занумеруем числами от 1 до $k$. Те вершины цвета 2, которые не соседствуют ни с какими вершинами цвета 1, перекрасим в цвет 1. Новая раскраска будет правильной, поэтому в ней $k$ цветов. Значит, какие-то вершины цвета 2 не перекрашены и потому соседствуют с вершинами цвета 1. Затем, вершины цвета 3, которые не соседствуют с вершинами цвета 2, не перекрашенными в цвет 1, перекрасим в цвет 2, и т. д. вплоть до последнего цвета. На каждом шаге получается правильная раскраска, поэтому хотя бы одна из вершин каждого цвета останется неперекрашенной.
После этого рассмотрим какую-либо вершину цвета $k$. Она не перекрашена, и потому соседствует с вершиной цвета k - 1. Эта вершина тоже не перекрашена, так как иначе ее первоначальный цвет был бы $k$, и она вначале соседствовала бы с вершиной того же цвета, что невозможно. Раз вершина не перекрашена, то она соседствует с вершиной цвета $k - 2$, и т. д. Продолжая этот процесс, построим путь длины $k$ из вершин $k$ цветов, которые не были перекрашены.
Граф - это набор вершин, причем некоторые из них соединены ребрами (каждое ребро соединяет ровно две вершины графа). Раскраска вершин графа называется правильной, если вершины одного цвета не соединены ребром. Некоторый граф правильно раскрашен в $k$ цветов, причем его нельзя правильно раскрасить в меньшее число цветов. Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех $k$ цветов ровно по одному разу.
Решение:
Цвета, в которые покрашен граф, занумеруем числами от 1 до $k$. Те вершины цвета 2, которые не соседствуют ни с какими вершинами цвета 1, перекрасим в цвет 1. Новая раскраска будет правильной, поэтому в ней $k$ цветов. Значит, какие-то вершины цвета 2 не перекрашены и потому соседствуют с вершинами цвета 1. Затем, вершины цвета 3, которые не соседствуют с вершинами цвета 2, не перекрашенными в цвет 1, перекрасим в цвет 2, и т. д. вплоть до последнего цвета. На каждом шаге получается правильная раскраска, поэтому хотя бы одна из вершин каждого цвета останется неперекрашенной.
После этого рассмотрим какую-либо вершину цвета $k$. Она не перекрашена, и потому соседствует с вершиной цвета k - 1. Эта вершина тоже не перекрашена, так как иначе ее первоначальный цвет был бы $k$, и она вначале соседствовала бы с вершиной того же цвета, что невозможно. Раз вершина не перекрашена, то она соседствует с вершиной цвета $k - 2$, и т. д. Продолжая этот процесс, построим путь длины $k$ из вершин $k$ цветов, которые не были перекрашены.
