В одной стране количество городов равно 81, каждый из них соединён дорогами не менее чем с 40 другими. Можно ли из каждого города добраться до другого?

Решение:

1. Рассмотрим любые два города и предположим, что между ними нет пути.

2. По условию, каждый из этих двух городов соединён не менее чем с 40 другими. Всего городов 81. Если предположить, что существует хотя бы два города, между которыми нет пути, то количество связей для каждого из этих городов должно быть меньше общего числа городов (81) минус 1 (сам город), то есть 80. Однако, если мы рассматриваем два таких изолированных города, то каждый из них связан не менее чем с 40 другими. Если предположить, что эти 40 городов являются общими для обоих