В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с семью другими. Верно ли, что из любого города можно добраться до любого другого, возможно, проезжая через другие города?
В случае ответа «да», запишите в ответ цифру 1, если «нет» — цифру 0.
Предположим, что есть два города, между которыми нет пути. Каждый из этих двух городов по условию соединен не менее, чем с семью другими городами, при этом все эти города различны — ведь если какие-то два из них совпадают, то существует путь, соединяющий исходные города (см. рис.). Но тогда в стране Семерка не менее 16 городов, что противоречит условию. Следовательно, наше предположение неверно, и любые два города связывает какой-то путь.