Решение задачи 340

Условие:

Двадцать городов соединены 172 авиалиниями. Доказать, что, используя эти авиалинии, можно из любого города перелететь в любой другой (быть может, делая пересадки).

Решение:

Интерпретируем эту задачу как граф: города -- вершины, авиалинии -- ребра. Докажем следующий факт: если у графа на n вершинах больше чем (n−1)(n−2)/2 ребер, то он связный. Доказывать будем по индукции.

База: n=3, по формуле в этом графе более чем 1 ребро, то есть хотя бы 2. Нетрудно видеть, что он связный.

Переход: Пусть для любого графа на n−1 вершине формула верна. Пусть дан граф на n вершинах, рассмотрим произвольную его вершину А. Сначала покажем, что из А выходят ребра: действительно, если из А не выходят ребра, то все ребра принадлежат графу на n−1 вершине, но в нем может быть максимум (n−1)(n−2)/2 ребер, если он полный, но по условию сказано, что ребер больше, чем (n−1)(n−2)/2. Если из А выходит n−1 ребро, то граф связный. Пусть из А выходит менее чем n−1 ребро, тогда на граф на n−1 вершине (который не содержит А) приходится более чем (n−2)(n−3)/2 ребер, а значит он связный по предположению индукции. А значит и исходный граф связан.

Возвращаемся к задаче, n=20, (n−1)(n−2)/2=19*18/2=171, 172>171, значит, граф связный.