Точка сочленения, эквивалентные определения

Следующие определения являются эквивалентными:

Определение:

(1) Точка сочленения графа [math]G[/math] - вершина, принадлежащая как минимум двум блокам [math]G[/math].

Определение:

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

Лемма:

Определения (1) и (2) эквивалентны.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]