Question

В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?

Answer 1

Изначально было 30⋅29/2=435 дорог. Для того чтобы из каждого города можно было проехать в каждый достаточно оставить 29 дорог (например, все дороги ведущие из какого-то одного города). Поэтому можно закрыть 435−29=406 дорог.