Question

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

Answer 1

Ответ:

Рассмотрим два произвольных города и предположим, что они не соединены путем, то есть такой последовательностью дорог, в которой начало очередной дороги совпадает с концом предыдущей. Каждый из этих двух городов по условию соединен не менее, чем с семью другими; при этом все упомянутые города различны – ведь если какие-то два из них совпадают, то есть путь, соединяющий исходные города.

 Таким образом, мы насчитали не менее 16 городов. Противоречие

Пошаговое объяснение: