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

Чтобы связь между 15 городами сохранялась, граф авиалиний должен оставаться связным. Связный граф на 15 вершинах требует не менее 14 рёбер; это достигается, например, если оставить авиалинии, образующие дерево.

Всего исходно имеется по одной линии между каждой парой городов: 15 · 14 ÷ 2 = 105. Значит, можно закрыть 105 − 14 = 91 линию.

Ответ: 91 авиалинию.