|
|
 |
Условие
В стране несколько городов, некоторые пары городов соединены двусторонними беспосадочными авиалиниями, принадлежащими k авиакомпаниям. Известно, что каждые две линии одной авиакомпании имеют общий конец. Докажите, что все города можно разбить на k + 2 группы так, что никакие два города из одной группы не соединены авиалинией.
Решение
Индукция по k.
База. Если k = 0, утверждение тривиально: авиалиний нет.
Шаг индукции. Рассмотрим граф, вершины которого соответствуют городам, а рёбра – авиалиниям.
Пусть E1, E2, ..., Ek – группы рёбер, соответствующие авиалиниям первой, второй, ..., k-й авиакомпаний. Нетрудно понять, что для любого i ∈ {1, ..., k} группа Ei – либо треугольник, либо ёж – несколько рёбер с одним концом. Если какая-то группа Ei – ёж с центром в вершине A, то удалим A и все выходящие из неё рёбра. В оставшемся графе рёбра принадлежат k – 1 авиакомпании, его вершины мы разобьём на k + 1 группу так, чтобы вершины из одной группы не были соединены ребром, а вершина A составит (k+2)-ю группу.
Остаётся рассмотреть случай, когда все группы E1, ..., Ek – треугольники. Тогда всего в графе 3k рёбер. Разобьём вершины графа на минимальное возможное количество групп так, что никакие две вершины одной группы не смежны.
Пусть это группы B1, ..., Bn, причём n ≥ k + 3. Отметим, что для каждых двух групп Bi и Bj существует ребро между вершиной из Bi и вершиной из Bj, иначе можно объединить эти две группы в одну. Таким образом, всего в графе хотя бы ½ n(n – 1) рёбер. Но ½ n(n – 1) ≥ (k + 3)(k + 2) > 3k. Противоречие.
