Изменения

== Алгоритм ==

{{Теорема

|statement=

#Удалим <tex>u</tex> из <tex>G</tex>. Докажем, что не существует пути из <tex>v</tex> в любого предка вершины <tex>u</tex>. Пусть это не так. Тогда <tex>\exists x \in T</tex> — предок <tex>u</tex> : <tex>\exists</tex> путь из <tex>v</tex> в <tex>x</tex> в <tex>G \backslash u</tex>. Пусть <tex>w</tex> — предпоследняя вершина на этом пути, <tex>w</tex> — потомок <tex>v</tex>. <tex>(w, x)</tex> — не ребро дерева <tex>T</tex>(в силу единственности пути в дереве) <tex>\Rightarrow (w, x)</tex> — обратное ребро, что противоречит условию.

#Пусть у <tex>root</tex> хотя бы два сына. Тогда при удалении <tex>root</tex> не существует пути между его поддеревьями, так как не существует перекрестных ребер <tex>\Rightarrow root</tex> — точка сочленения.

<tex>\Rightarrow</tex>

#Докажем что из отрицания второго утверждения следует отрицание первого. Обозначим через <tex>G'</tex> граф, состоящий из вершин, не являющихся потомками <tex>u</tex>. Удалим вершину <tex>u</tex>. Очевидно, что граф <tex>G'</tex> и все поддеревья вершины <tex>u</tex> останутся связными, кроме того из каждого поддерева есть ребро в <tex>G' \Rightarrow G \backslash u</tex> — связный <tex>\Rightarrow u</tex> — не точка сочленения.