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

Представим города вершинами графа, а дороги — рёбрами. Если бы из какого-либо города нельзя было добраться до некоторых других, граф был бы несвязным и распался бы как минимум на две компоненты.

В каждой компоненте должно быть не менее 8 городов: у каждого города есть дороги как минимум к 7 другим, и все они должны находиться в той же компоненте. Две такие компоненты содержали бы не менее 16 городов, но в стране всего 15.

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