Задача
COM-B2-M07-P007 Удаление ребра цикла
#7
★★★☆☆ Уровень 3 из 5
Докажите, что если из связного графа удалить одно ребро, лежащее на цикле, то граф останется связным.
На цикле есть обходной путь между концами удалённого ребра.
Пусть удаляемое ребро соединяет \(u\) и \(v\). Так как оно лежит на цикле, после удаления этого ребра на оставшейся части цикла всё ещё есть путь из \(u\) в \(v\).
Любой путь в исходном графе, использовавший ребро \(uv\), можно заменить: вместо \(uv\) пройти по этому обходному пути. Значит, связность не нарушается.
Базовая лемма для построения остовного дерева.