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

Предыдущий
вопрос Следующий
вопрос

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

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

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

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

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