|
|
 |
Условие
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более N различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на N + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
Решение
Рассмотрим граф с вершинами в городах, рёбра которого соответствуют дорогам. Из условия следует, что в этом графе через каждую вершину проходит не более N нечётных циклов.
Докажем индукцией по количеству вершин, что вершины такого графа можно
покрасить в N + 2 цвета так, чтобы никакие две вершины одного цвета не были соединены ребром.
База для графа из одной вершины очевидна.
Шаг индукции. Пусть утверждение верно для графа, в котором менее k вершин. Рассмотрим граф G с k вершинами, в котором через каждую вершину проходит не более N нечётных циклов. Удалив из этого графа любую вершину A и все выходящие из неё рёбра, мы получим граф H с k – 1 вершиной. Очевидно, через каждую вершину графа H проходит не более N циклов нечётной длины.
Тогда покрасим вершины графа H в N + 2 цвета таким образом, чтобы никакие две вершины одного цвета не были соединены ребром (это можно сделать по индуктивному предположению).
Для цвета k (2 ≤ k ≤ N + 2) рассмотрим граф H1k из всех вершин графа H, покрашенных в цвета 1 и k, и всех проведённых между ними рёбер графа G. Поскольку никакие две вершины одинакового цвета в графе H1k не соединены ребром, то в этом графе нет циклов нечётной
длины. Построим граф G1k, добавив к графу H1k вершину A и все выходящие из неё к вершинам H1k рёбра.
Если для некоторого k в графе G1k через
вершину A не проходит ни один цикл нечётной длины, то циклов нечётной длины в этом графе нет. В этом случае несложно доказать (см. лемму к задаче 110038), что мы можем так перекрасить вершины графа G1k (используя лишь цвета 1 и k), что все рёбра в этом графе будут соединять пары вершин разных цветов. Так как все остальные вершины графа G покрашены в цвета, отличные от 1 и k, то и во всём графе G никакие две вершины одинакового цвета не соединены ребром.
Остаётся рассмотреть случай, когда для каждого k (2 ≤ k ≤ N + 2) в графе G1k через вершину A проходит хотя бы один цикл нечётной длины.
Заметим, что такой нечётный цикл проходит только по вершинам цветов 1 и k, причём среди них есть хотя бы одна вершина цвета k. Следовательно, через вершину A проходит хотя бы N + 1 цикл нечётной длины, что противоречит условию. Следовательно, этот случай невозможен, и требуемая раскраска получена.
