Олимпиадная задача по теории графов для 8-10 классов от Берлова, Дольникова и Карпова

  Рассмотрим граф с вершинами в городах, рёбра которого соответствуют дорогам. Из условия следует, что в этом графе через каждую вершину проходит не более N нечётных циклов.

  Докажем индукцией по количеству вершин, что вершины такого графа можно покрасить в  N + 2  цвета так, чтобы никакие две вершины одного цвета не были соединены ребром.

  База для графа из одной вершины очевидна.

  Шаг индукции. Пусть утверждение верно для графа, в котором менее k вершин. Рассмотрим граф G с k вершинами, в котором через каждую вершину проходит не более N нечётных циклов. Удалив из этого графа любую вершину A и все выходящие из неё рёбра, мы получим граф H с  k – 1  вершиной. Очевидно, через каждую вершину графа H проходит не более N циклов нечётной длины. Тогда покрасим вершины графа H в  N + 2  цвета таким образом, чтобы никакие две вершины одного цвета не были соединены ребром (это можно сделать по индуктивному предположению).

  Для цвета k  (2 ≤ k ≤ N + 2)  рассмотрим граф H_1k из всех вершин графа H, покрашенных в цвета 1 и k, и всех проведённых между ними рёбер графа G. Поскольку никакие две вершины одинакового цвета в графе H_1k не соединены ребром, то в этом графе нет циклов нечётной длины. Построим граф G_1k, добавив к графу H_1k вершину A и все выходящие из неё к вершинам H_1k рёбра.

  Если для некоторого k в графе G_1k через вершину A не проходит ни один цикл нечётной длины, то циклов нечётной длины в этом графе нет. В этом случае несложно доказать (см. лемму к задаче 210038), что мы можем так перекрасить вершины графа G_1k (используя лишь цвета 1 и k), что все рёбра в этом графе будут соединять пары вершин разных цветов. Так как все остальные вершины графа G покрашены в цвета, отличные от 1 и k, то и во всём графе G никакие две вершины одинакового цвета не соединены ребром.

  Остаётся рассмотреть случай, когда для каждого k  (2 ≤ k ≤ N + 2)  в графе G_1k через вершину A проходит хотя бы один цикл нечётной длины.

  Заметим, что такой нечётный цикл проходит только по вершинам цветов 1 и k, причём среди них есть хотя бы одна вершина цвета k. Следовательно, через вершину A проходит хотя бы  N + 1  цикл нечётной длины, что противоречит условию. Следовательно, этот случай невозможен, и требуемая раскраска получена.

Ответ задачи отсутствует