В некой стране 30 городов, при этом каждый соединен с каждым дорогой.

Представим городка, как верхушки графа, а дороги, как рёбра.

Вначале у нас был полный граф на 30 вершин, как следует, в нём было (30 * 29 : 2 = 435) рёбер. Минимальный связный граф - дерево. В дереве на 30-ти вершинах будет 29 рёбер, следовательно, убрать можно не более (435 - 29 = 406) рёбер. Пример - уберём все рёбра из полного графа на 29 вершин, тогда уберётся (29 * 28 : 2 = 406) рёбер, а из хоть какой вершины можно будет добраться до иной через 30-ую верхушку, которую мы не трогали.

Ответ: 406 дорог.