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

Рассмотрим граф: города — вершины, дороги — рёбра. Предположим, что граф несвязный. Тогда в каждой его компоненте связности должно быть не менее 8 вершин: у любой вершины есть как минимум 7 соседей, и все они находятся в той же компоненте.

Но в двух или более компонентах тогда было бы не менее 16 вершин, тогда как всего городов 15. Получили противоречие.

Ответ: да. Из любого города можно добраться до любого другого.