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