Изменения

(1) Точка сочленения [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа ]] <mathtex>G</mathtex> - вершина, принадлежащая как минимум двум блокам <mathtex>G</mathtex>.

(2) Точка сочленения графа <mathtex>G</mathtex> - вершина, при удалении которой в <mathtex>G</mathtex> увеличивается число компонент связности.}}

{{УтверждениеЛемма

(1 ⇒ 2) Пусть вершина <mathtex>v</mathtex> принадлежит некоторым блокам <mathtex>A</mathtex> и <mathtex>B</mathtex>. Вершине <mathtex>v</mathtex> инцидентны некоторые ребра <mathtex>e=uv \in A</mathtex> и <mathtex>f=wv \in B</mathtex>. Ребра <mathtex>e</mathtex> и <mathtex>f</mathtex> находятся в различных блоках, поэтому не существует пары непересекающихся путей между их концами. Один из этих путей может состоять только из <mathtex>v</mathtex>, поэтому любой путь, соединяющий <mathtex>u</mathtex> и <mathtex>w</mathtex>, пройдет через <mathtex>v</mathtex>. При удалении <mathtex>v</mathtex> между <mathtex>u</mathtex> и <mathtex>w</mathtex> не останется путей, и одна из компонент связности распадется на две. (2 ⇒ 1) Пусть <mathtex>v</mathtex> принадлежала только одному блоку <mathtex>C</mathtex>. Все вершины <mathtex>u_1...u_n</mathtex>, смежные с <mathtex>v</mathtex>, также лежат в <mathtex>C</mathtex> (в силу рефлексивности отношения вершинной двусвязности). Теперь удалим <mathtex>v</mathtex>. Но <mathtex>u_1...u_n</mathtex> были концами ребер, удаленных из <mathtex>C</mathtex> вместе с <mathtex>v</mathtex>, поэтому между каждой парой из них остался путь.Рассмотрим <mathtex>D</mathtex> - компоненту связности, в которой лежала <mathtex>v</mathtex>. Пусть между вершинами <mathtex>u, w \in D</mathtex> существовал путь, проходящий через <mathtex>v</mathtex>. Но он проходил также через некоторые вершины из <mathtex>u_1...u_n</mathtex>, связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.