Задача
COM-B2-M04-P006 Связный граф и дерево
Докажите, что из любого конечного связного графа можно удалить несколько рёбер так, чтобы граф остался связным и перестал содержать циклы.
Выберите среди связных остовных подграфов тот, где рёбер меньше всего.
Рассмотрим все связные подграфы, содержащие все вершины исходного графа. Среди них выберем подграф \(H\) с минимальным числом рёбер. Такой подграф существует, так как исходный граф входит в рассмотрение.
Если в \(H\) есть цикл, удалим одно ребро этого цикла. Между его концами всё ещё есть путь по остальной части цикла, поэтому связность не нарушается. Получается связный остовный подграф с меньшим числом рёбер, противоречие.
Значит, циклов в \(H\) нет. Искомый граф получен удалением лишних рёбер.
Это фактически доказательство существования остовного дерева.