Задача 042 — Задачи на Графы

Каждые два из 21 города соединены прямым рейсом одной из четырёх авиакомпаний. Докажите, что существует замкнутый маршрут из четырех рейсов одной авиакомпании.

Подсказка

Решение

Все маршруты образуют полный граф на 21 вершине, рёбра которого раскрашены в 4 цвета. Если искомого замкнутого маршрута нет, любые две вершины этого графа связаны не более чем одним одноцветным маршрутом длины 2. Стало быть, всего таких маршрутов не более, чем $4 C_{21}^{2}=840$ . С другой стороны, пусть из данной вершины выходит $a, b, c$ и $d$ рёбер первого, второго, третьего и четвёртого цветов соответственно. Тогда число одноцветных маршрутов длины 2 , для которых эта вершина — средняя, равно $(a(a-1)+b(b-1)+c(c- 1)+d(d-1)) / 2=\left(a^{2}+b^{2}+c^{2}+d^{2}-(a+b+c+d)\right) / 2=\left(a^{2}+b^{2}+c^{2}+d^{2}\right) / 2-10$ . По неравенству между средним арифметическим и средним квадратическим имеем: $a^{2}+b^{2}+c^{2}+d^{2} \geq(a+b+c+d)^{2} / 4=100$ . Таким образом, каждая вершина нашего графа является средней минимум для $100 / 2-10=40$ одноцветных маршрутов, причём минимум достигается только в случае, когда из вершины выходит ровно по 5 маршрутов каждого цвета. И только в этом случае сумма количеств одноцветных маршрутов длины 2 по всем вершинам равна 840, в остальных — больше. Но такой случай невозможен, потому что тогда, оставив в нашем графе только рёбра одного какого-то цвета, мы получили бы граф с нечётным числом нечётных вершин.