Question

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

Answer 1

В стране 25 * 24 / 2 = 300 дорог.

Если оставить 23 или меньше дорог, как минимум один город будет не связан с другими (выбираем произвольный город и начинаем открывать дороги, каждое открытие добавляет к списку городов, в которые можно добраться, не более чем 1 новый город), а 24 дороги оставить можно: например, выбрать один город и связать его с остальными.

Закрыть можно не более 300 - 24 = 276 дорог.