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