Для доказательства этого утверждения воспользуемся методом математической индукции.

Пусть утверждение верно для 15 городов. Докажем его для 16 городов.

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

Теперь рассмотрим город B, с которым соединен один из выбранных 7 городов. По предположению индукции, из города B можно доехать до любого другого города. Следовательно, из города A также можно доехать до любого другого города.

Таким образом, из любого города 15 можно доехать до любого другого города, что и требовалось доказать.