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

Решение:

Для того чтобы связный граф стал деревом, необходимо, чтобы в нем не было циклов. Дерево с \( |V| \) вершинами имеет \( |V| - 1 \) рёбер. В данном графе \( |V| = 8 \), следовательно, в дереве должно быть \( 8 - 1 = 7 \) рёбер.

Исходный граф имеет 12 рёбер. Чтобы получить дерево, нужно удалить лишние рёбра, которые образуют циклы.

Количество рёбер, которое нужно удалить, равно разнице между текущим количеством рёбер и количеством рёбер в дереве:

\( 12 - 7 = 5 \) рёбер.

Ответ: 5.