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