В некотором связном графе 8 вершин и 12 рёбер. Сколько рёбер нужно удалить из этого графа, чтобы получившийся граф оказался деревом?

В связном графе можно оставить рёбра некоторого остовного дерева. Оно сохраняет все 8 вершин и связность, а число его рёбер равно 8 − 1 = 7.

Тогда нужно удалить 12 − 7 = 5 рёбер. Удалять следует рёбра, не нарушая связность оставшегося графа.

Ответ: 5 рёбер.