№ 15. В стране Семёрка 15 городов, каждый из которых соединён дорогами не менее чем с семью другими. Верно ли, что из любого города можно добраться до любого другого, возможно, проезжая через другие города? В случае ответа «да» запишите в ответ цифру 1, если «нет» — цифру 0.

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

Ответ: 1.