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