Изменения

Пусть <tex>T</tex> - дерево [[Обход в глубину, цвета вершин|обхода в глубину]], <tex>root</tex> - корень <tex>T</tex>. Вершина <tex>u \ne root</tex> - точка сочленения <tex>\Leftrightarrow \exists v \in T</tex> - сын <tex>u</tex> : из <tex>v</tex> или любого потомка вершины <tex>v</tex> нет обратного ребра в предка вершины <tex>u</tex>. <tex>root</tex> - точка сочленения <tex>\Leftrightarrow root</tex> имеет хотя бы двух сыновей в дереве поиска в глубину.

|proof=

<tex>\Leftarrow</tex>

#Удалим <tex>u</tex> из <tex>G</tex>. Докажем, что <tex>\nexists</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> - точка сочленения и у него есть только 1 сын. Тогда при удалении <tex>root</tex> остается дерево с корнем в его сыне, содержащее все остальные вершины графа, то есть оставшийся граф связен - противоречие с тем, что <tex>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> - не точка сочленения.

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