6–7. В стране 1974 города. Из столицы выходит 101 авиалиния, а из города Дальний — одна авиалиния. Из всех остальных городов выходит по 20 авиалиний. Доказать, что из столицы можно прилететь в Дальний, возможно, с пересадками.

Рассмотрим города и авиалинии как граф. Если направление авиалиний учитывается, заменим каждую линию неориентированным ребром: связность такого графа означает возможность добраться по маршруту, следуя направлениям рейсов лишь при соответствующих выходящих линиях; обычно в этой задаче линии рассматриваются как соединения городов.

У столицы 101 инцидентная линия, у Дальнего — 1, у каждого из остальных 1972 городов — 20. Все степени вершин нечётны: 101 и 1 нечётны, а 20 чётно. Однако число вершин нечётной степени в любом графе чётно, и здесь оно равно 1974.

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

Ответ: из столицы можно добраться в Дальний с пересадками.