Задача
COM-B2-M07-P005 Добавленное ребро
#5
★★☆☆☆ Уровень 2 из 5
В дерево добавили одно ребро между двумя уже имеющимися вершинами. Докажите, что появился ровно один цикл.
В дереве между концами нового ребра был единственный путь.
Пусть новое ребро соединяет вершины \(u\) и \(v\). В дереве между \(u\) и \(v\) был ровно один простой путь. Этот путь вместе с новым ребром образует цикл.
Другого цикла быть не может: любой цикл, появившийся после добавления, обязан использовать новое ребро, потому что раньше циклов не было. Тогда оставшаяся часть цикла была бы другим путём между \(u\) и \(v\) в дереве, что невозможно.
Ключевой факт для задач с \(n\) рёбрами на \(n\) вершинах.