Олимпиадная задача по теории графов и комбинаторике для 9–11 классов — Богданов, Челноков

  Рассмотрим граф, вершины которого – это города, а рёбра – авиалинии. Обобщим задачу – разрешим графу иметь кратные рёбра. При этом для каждого набора из k вершин количество рёбер между ними не превосходит  2k – 2.  Требуется доказать, что можно покрасить рёбра графа в два цвета так, чтобы не было одноцветных циклов.

  Назовём непустое подмножество A вершин графа критическим, если количество рёбер графа между вершинами множества A – ровно  2|A| – 2.   Лемма. Если A и B – критические подмножества, причём A ∩ B ≠ ∅,  то A ∪ B – тоже критическое.

  Доказательство. Пусть  C = A ∩ B,  D = A ∪ B  и  D – не критическое. Пусть  |A| = a,  |B| = b,  |C| = c,  |D| = d = a + b – c.   Так как количество рёбер в A равно  2a – 2,  а количество рёбер в D меньше чем  2d – 2,  то число рёбер, соединяющих вершины из D, у которых не оба конца лежат в A, меньше

(2d – 2) – (2a – 2) = 2(d – a) = 2(b – c).  В частности, в число этих рёбер входят все рёбра, соединяющие вершины B, не обе из которых лежат в C. Поэтому их число также меньше  2(b – c),  а число остальных рёбер среди вершин B – больше  (2b – 2) – 2(b – c) = 2c – 2.  Но это в точности рёбра, соединяющие вершины множества C; значит, C не удовлетворяет условию задачи. Противоречие.

  Заметим, что в условиях леммы множество C также будет критическим.   Перейдём к решению задачи. Предположим противное и рассмотрим граф с минимальным числом вершин n, для которого утверждение задачи не выполняется. Рассмотрим все его вершины. Число рёбер между ними не больше  2n – 2.  Если степень каждой вершины не меньше 4, то общее количество рёбер не меньше  4n : 2 = 2n > 2n – 2,  что невозможно. Значит, найдётся вершина a степени не больше 3. Если её степень меньше 3, то выкинем её; рёбра оставшегося графа можно покрасить требуемым образом, так как он, очевидно, удовлетворяет условию. Покрасив после этого ребра из вершины a в разные цвета, мы, очевидно, не образуем одноцветных циклов, и требуемая раскраска получена.

  Итак, степень a равна 3, и она соединена с вершинами b, c, d. Все три вершины b, c, d не могут совпадать, так как иначе между двумя вершинами a и b было бы больше  2·2 – 2  рёбер, что невозможно. Тогда среди b, c и d есть вершина, отличная от обеих остальных – пусть это вершина c.

  Выбросим из графа вершину a. Если в оставшемся графе пара вершин b и c не принадлежит одновременно никакому критическому подмножеству, то после добавления фиктивного ребра  (b, c)  мы получим граф, удовлетворяющий условию задачи, число вершин в котором меньше, чем в нашем (см. рис.). Покрасим его рёбра требуемым образом, потом удалим добавленное ребро, вернём вершину a и покрасим рёбра  (a, b)  и  (a, c)  в цвет фиктивного ребра, а ребро  (a, d)  в другой. Очевидно, одноцветных циклов не появится.

  Аналогично можем поступить, еслиcиdодновременно не принадлежат критическому множеству. Если же вершиныbиcпринадлежат критическому множествуA₁, а вершиныcиd– критическому множествуA₂, то  A₁∪A₂  – тоже критическое (ибо  c∈A₁∩A₂).  Но тогда, добавив к этому множеству вершинуa, мы добавим к его внутренним рёбрам три ребра; следовательно, полученное множество противоречит условию задачи.

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