Изменения

Удалим <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>