Разделы 
Дополнительно
Задача по математике - 1599
2019-01-19 
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более $N$ различных несамопересекающихся циклических маршрутов нечетной длины. Докажите, что страну можно разделить на $2N + 2$ республики так, чтобы никакие два города из одной республики не были соединены дорогой.
Решение:
Построим граф $G$ с вершинами в городах, ребра которого соответствуют дорогам. Докажем, что вершины этого графа можно покрасить в $2N + 2$ цвета правильным образом (т. е. так, чтобы никакие две вершины одинакового цвета не были соединены ребром). Это равносильно утверждению задачи.
Выберем по одному ребру в каждом нечетном цикле графа $G$. Назовем эти ребра плохими, а остальные - хорошими. Удалив из графа $G$ плохие ребра, мы получим граф, в котором нет циклов нечетной длины.
Лемма. Вершины графа без нечетных циклов можно раскрасить правильным образом в два цвета.
Доказательство. Достаточно доказать лемму для связного графа. Выберем вершину $A$ и припишем каждой вершине число, равное минимальной длине пути до нее из $A$. Тогда два одинаковых числа не стоят рядом (иначе есть нечетный цикл). Раскрасив все четные вершины в один цвет, а нечетные - в другой, получим требуемое.
Таким образом, вершины графа $G$ можно покрасить в два цвета (пусть это цвета $a$ и $b$) так, что никакие две вершины одного цвета не были соединены хорошим ребром.
Поскольку через каждую вершину графа $G$ проходит не более $N$ нечетных циклов, а в каждом из них мы отметили одно ребро, то из каждой вершины выходит не более $N$ плохих ребер. Следовательно, мы можем раскрасить вершины графа $G$ в $N +1$ цвет так, чтобы никакие две из них не были соединены в графе $G$ плохим ребром. (Будем красить вершины по очереди. Добавляя очередную вершину $A$, заметим, что среди покрашенных ранее она соединена плохими ребрами не более, чем с $N$ вершинами, следовательно, мы можем покрасить вершину $A$ в цвет, отличный от цветов ранее покрашенных вершин, соединенных с $A$ плохими ребрами.)
Итак, покрасим вершины графа $G$ в цвета $1, 2, 3,\cdots, (N +1)$ так, чтобы никакие две из них не были соединены плохим ребром. После этого у всех вершин изменим оттенок на светлый, если в первой раскраске она была покрашена в цвет $\alpha$, и на темный, если она была покрашена в цвет $\beta$. В полученной раскраске используется $2N + 2$ цвета (с учетом оттенков) и никакие две вершины одного цвета не соединены ребром.
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более $N$ различных несамопересекающихся циклических маршрутов нечетной длины. Докажите, что страну можно разделить на $2N + 2$ республики так, чтобы никакие два города из одной республики не были соединены дорогой.
Решение:
Построим граф $G$ с вершинами в городах, ребра которого соответствуют дорогам. Докажем, что вершины этого графа можно покрасить в $2N + 2$ цвета правильным образом (т. е. так, чтобы никакие две вершины одинакового цвета не были соединены ребром). Это равносильно утверждению задачи.
Выберем по одному ребру в каждом нечетном цикле графа $G$. Назовем эти ребра плохими, а остальные - хорошими. Удалив из графа $G$ плохие ребра, мы получим граф, в котором нет циклов нечетной длины.
Лемма. Вершины графа без нечетных циклов можно раскрасить правильным образом в два цвета.
Доказательство. Достаточно доказать лемму для связного графа. Выберем вершину $A$ и припишем каждой вершине число, равное минимальной длине пути до нее из $A$. Тогда два одинаковых числа не стоят рядом (иначе есть нечетный цикл). Раскрасив все четные вершины в один цвет, а нечетные - в другой, получим требуемое.
Таким образом, вершины графа $G$ можно покрасить в два цвета (пусть это цвета $a$ и $b$) так, что никакие две вершины одного цвета не были соединены хорошим ребром.
Поскольку через каждую вершину графа $G$ проходит не более $N$ нечетных циклов, а в каждом из них мы отметили одно ребро, то из каждой вершины выходит не более $N$ плохих ребер. Следовательно, мы можем раскрасить вершины графа $G$ в $N +1$ цвет так, чтобы никакие две из них не были соединены в графе $G$ плохим ребром. (Будем красить вершины по очереди. Добавляя очередную вершину $A$, заметим, что среди покрашенных ранее она соединена плохими ребрами не более, чем с $N$ вершинами, следовательно, мы можем покрасить вершину $A$ в цвет, отличный от цветов ранее покрашенных вершин, соединенных с $A$ плохими ребрами.)
Итак, покрасим вершины графа $G$ в цвета $1, 2, 3,\cdots, (N +1)$ так, чтобы никакие две из них не были соединены плохим ребром. После этого у всех вершин изменим оттенок на светлый, если в первой раскраске она была покрашена в цвет $\alpha$, и на темный, если она была покрашена в цвет $\beta$. В полученной раскраске используется $2N + 2$ цвета (с учетом оттенков) и никакие две вершины одного цвета не соединены ребром.
