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

Смотри, тут всё просто: нужно доказать, что в стране «Семёрка» все города связаны между собой, как вагончики в поезде.

Доказательство:

• Предположим, что есть два города — А и В, между которыми нельзя проехать напрямую. Это значит, что они находятся в разных «частях страны» и не соединены дорогами.
• У города А есть не менее 7 других городов, с которыми он соединён. То же самое у города В.
• Так как всего городов 15, то 7 городов, соединённых с А, плюс 7 городов, соединённых с В, составляют 14 городов. Но тогда не остаётся городов, через которые можно было бы соединить А и В, чтобы выполнить условие задачи.
• Получается противоречие: мы предположили, что нет пути между А и В, но это невозможно, так как все города должны быть соединены.

Вывод: Из любого города в стране «Семёрка» можно проехать в любой другой город.