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

Допустим, что нельзя добраться из города А в город Б. Из города А должно выходить, как минимум, 7 дорог в соседние города. В город Б ни одна из них не ведёт, так как по нашему предположению туда нельзя добраться из А. Значит, существует по крайней мере 8 городов, из которых нельзя добраться в Б. Из города Б тоже должно выходить 7 дорог, ни одна из которых не приведёт в А и, значит, существует 8 городов, из которых нельзя добраться в А. Выходит, что в таком случае городов не меньше, чем 16. Получили противоречие. Значит, предположение неверно и из любого города можно проехать в любой другой.