Изменения
→Алгоритм
<tex> \Leftarrow</tex> <br>
Удалим <tex> (u, v)</tex> из <tex> G</tex>. Докажем, что мы не сможем достичь ни одного из предков <tex> v </tex> (в частности <tex> u </tex>). Докажем этот факт от противного.
Пусть это не так, и <tex> w</tex> - предпоследняя вершина на пути от <tex> v</tex> до ее предка <tex>x </tex>. Очевидно, <tex> (w, x)</tex> не ребро дерева (в силу единственности пути в дереве). Если <tex> (w, x)</tex> - обратное ребро, то это противоречит условию теоремы, так как <tex> x</tex> - предок <tex> u</tex>. Следовательно мы не достигнем предков <tex>v</tex>, а значит количество компонент связности увеличилось, что значит поэтому ребро <tex>(u, v)</tex> является мостом.<br>
<tex> \Rightarrow</tex> <br>
Пусть существует удовлетворяющее условию обратное ребро <tex>(x, w)</tex>. Тогда <tex>(u, v)</tex> лежит на цикле <tex>x \rightsquigarrow v \rightarrow u \rightsquigarrow w \rightarrow x</tex> и не может быть мостом.
