Олимпиадная задача по теории графов от Дольникова — разбиение городов по авиалиниям

  Индукция по k.

  База. Если  k = 0,  утверждение тривиально: авиалиний нет.

  Шаг индукции. Рассмотрим граф, вершины которого соответствуют городам, а рёбра – авиалиниям.

  Пусть E₁, E₂, ..., E_k – группы рёбер, соответствующие авиалиниям первой, второй, ..., k-й авиакомпаний. Нетрудно понять, что для любого  i ∈ {1, ..., k}  группа E_i – либо треугольник, либо ёж – несколько рёбер с одним концом. Если какая-то группа E_i – ёж с центром в вершине A, то удалим A и все выходящие из неё рёбра. В оставшемся графе рёбра принадлежат  k – 1  авиакомпании, его вершины мы разобьём на  k + 1  группу так, чтобы вершины из одной группы не были соединены ребром, а вершина A составит (k+2)-ю группу.

  Остаётся рассмотреть случай, когда все группы E₁, ..., E_k – треугольники. Тогда всего в графе 3k рёбер. Разобьём вершины графа на минимальное возможное количество групп так, что никакие две вершины одной группы не смежны.

  Пусть это группы B₁, ..., B_n, причём  n ≥ k + 3.  Отметим, что для каждых двух групп B_i и B_j существует ребро между вершиной из B_i и вершиной из B_j, иначе можно объединить эти две группы в одну. Таким образом, всего в графе хотя бы  ½ n(n – 1)  рёбер. Но  ½ n(n – 1) ≥ (k + 3)(k + 2) > 3k.   Противоречие.

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