Из города Стольный выходит 15 дорог, из города Дальний - 1 дорога, из каждого другого города - по 4 дороги Докажите, что из Стольного можно доехать до Дальнего.

Рассмотрим все города, до которых можно доехать из Стольного и сам город

Стольный и подсчитаем количество всех выходящих из них дорог. Тогда, каждую дорогу, проходящую между этими городами посчитаем дважды. Тогда среди рассмотренных городов должен быть город Дальний, так как в противном случае мы рассмотрим ровно один город с нечетным числом дорог, и получим нечетную сумму.

Если среди рассматриваемых нами городов нет Дальнего, то мы рассматриваем Стольный, из которого выходит 15 дорог и еще несколько городов, из которых входит по 4 дороги и сумма входящих из них дорог равна:

15 + 4 х n, то есть она нечетна.

Значит, Дальний входит в число городов, до которых можно доехать из Стольного.