Разделы 
Дополнительно
Задача по математике - 1606
2019-01-19 
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более $N$ различных несамопересекающихся циклических маршрутов нечетной длины. Докажите, что страну можно разделить на $N + 2$ республики так, чтобы никакие два города из одной республики не были соединены дорогой.
Решение:
Рассмотрим граф с вершинами в городах, ребра которого соответствуют дорогам. Из условия следует, что в этом графе через каждую вершину проходит не более $N$ нечетных циклов.
Докажем индукцией по количеству вершин, что вершины такого графа можно покрасить в $N + 2$ цвета так, чтобы никакие две вершины одного цвета не были соединены ребром. База индукции для графа из одной вершины очевидна, докажем индуктивный переход. Пусть утверждение верно для графа, в котором менее $k$ вершин. Рассмотрим граф $G$ с $k$ вершинами, в котором через каждую вершину проходит не более $N$ нечетных циклов. Удалив из этого графа любую вершину $A$ и все выходящие из нее ребра, мы получим граф , $G^{ \prime }$ с $k - 1$ вершиной. Очевидно, через каждую вершину графа $, G^{ \prime} $ проходит не более $N$ циклов нечетной длины. Тогда покрасим вершины графа $G^{ \prime}$ в $N + 2$ цвета таким образом, чтобы никакие две вершины одного цвета не были соединены ребром (это можно сделать по индуктивному предположению).
Для цвета $k$ (где $2 \leq k \leq (N + 2))$ рассмотрим граф $G^{ \prime}_{1k}$ из всех вершин графа $G^{ \prime}$, покрашенных в цвета 1 и $k$, и всех проведенных между ними ребер графа $G$. Поскольку никакие две вершины одинакового цвета в графе $G^{ \prime}_1k$ не соединены ребром, то в этом графе нет циклов нечетной длины. Построим граф $G_{1k}$, добавив к графу $G^{ \prime}_{1k}$ через вершину $A$ и все выходящие из нее к вершинам $G^{ \prime}_{1k}$ ребра.
Если для некоторого $k$ в графе $G_{1k}$ через вершину $A$ не проходит ни один цикл нечетной длины, то циклов нечетной длины в этом графе нет. В этом случае несложно доказать (см. лемму к задаче 1599), что мы можем так перекрасить вершины графа $G_{1k}$ (используя лишь цвета 1 и $k$), что все ребра в этом графе будут соединять пары вершин разных цветов. Так как все остальные вершины графа $G$ покрашены в цвета, отличные от 1 и $k$, то и во всем графе $G$ никакие две вершины одинакового цвета не соединены ребром.
Остается рассмотреть случай, когда для каждого $к$ (где $2 \leq к \leq N+2)$ в графе $G_{1k}$ через вершину $A$ проходит хотя бы один цикл нечетной длины. Заметим, что такой нечетный цикл проходит только по вершинам цветов 1 и $к$, причем среди них есть хотя бы одна вершина цвета $к$. Следовательно, через вершину $A$ проходит хотя бы $N + 1$ цикл нечетной длины, что противоречит условию. Следовательно, этот случай невозможен, и требуемая раскраска получена.
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более $N$ различных несамопересекающихся циклических маршрутов нечетной длины. Докажите, что страну можно разделить на $N + 2$ республики так, чтобы никакие два города из одной республики не были соединены дорогой.
Решение:
Рассмотрим граф с вершинами в городах, ребра которого соответствуют дорогам. Из условия следует, что в этом графе через каждую вершину проходит не более $N$ нечетных циклов.
Докажем индукцией по количеству вершин, что вершины такого графа можно покрасить в $N + 2$ цвета так, чтобы никакие две вершины одного цвета не были соединены ребром. База индукции для графа из одной вершины очевидна, докажем индуктивный переход. Пусть утверждение верно для графа, в котором менее $k$ вершин. Рассмотрим граф $G$ с $k$ вершинами, в котором через каждую вершину проходит не более $N$ нечетных циклов. Удалив из этого графа любую вершину $A$ и все выходящие из нее ребра, мы получим граф , $G^{ \prime }$ с $k - 1$ вершиной. Очевидно, через каждую вершину графа $, G^{ \prime} $ проходит не более $N$ циклов нечетной длины. Тогда покрасим вершины графа $G^{ \prime}$ в $N + 2$ цвета таким образом, чтобы никакие две вершины одного цвета не были соединены ребром (это можно сделать по индуктивному предположению).
Для цвета $k$ (где $2 \leq k \leq (N + 2))$ рассмотрим граф $G^{ \prime}_{1k}$ из всех вершин графа $G^{ \prime}$, покрашенных в цвета 1 и $k$, и всех проведенных между ними ребер графа $G$. Поскольку никакие две вершины одинакового цвета в графе $G^{ \prime}_1k$ не соединены ребром, то в этом графе нет циклов нечетной длины. Построим граф $G_{1k}$, добавив к графу $G^{ \prime}_{1k}$ через вершину $A$ и все выходящие из нее к вершинам $G^{ \prime}_{1k}$ ребра.
Если для некоторого $k$ в графе $G_{1k}$ через вершину $A$ не проходит ни один цикл нечетной длины, то циклов нечетной длины в этом графе нет. В этом случае несложно доказать (см. лемму к задаче 1599), что мы можем так перекрасить вершины графа $G_{1k}$ (используя лишь цвета 1 и $k$), что все ребра в этом графе будут соединять пары вершин разных цветов. Так как все остальные вершины графа $G$ покрашены в цвета, отличные от 1 и $k$, то и во всем графе $G$ никакие две вершины одинакового цвета не соединены ребром.
Остается рассмотреть случай, когда для каждого $к$ (где $2 \leq к \leq N+2)$ в графе $G_{1k}$ через вершину $A$ проходит хотя бы один цикл нечетной длины. Заметим, что такой нечетный цикл проходит только по вершинам цветов 1 и $к$, причем среди них есть хотя бы одна вершина цвета $к$. Следовательно, через вершину $A$ проходит хотя бы $N + 1$ цикл нечетной длины, что противоречит условию. Следовательно, этот случай невозможен, и требуемая раскраска получена.
