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

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

В компоненте из не более чем 7 городов каждый город соединён дорогами максимум с 6 другими городами. Это противоречит условию, что у каждого города не менее 7 соседей.

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