Изменения

Пусть граф <mathtex>G</mathtex> [[Отношение реберной двусвязности|реберно двусвязен]]. Обозначим <mathtex>A_1...A_n</mathtex> - компоненты реберной двусвязности, а <mathtex>a_1...a_m</mathtex> - [[Мост, эквивалентные определения|мосты]] <mathtex>G</mathtex>.Построим граф <mathtex>T</mathtex>, в котором вершинами будут <mathtex>A_1...A_n</mathtex>, а ребрами <mathtex>a_1...a_m</mathtex>, соединяющими соответствующие вершины из соответствующих компонент реберной двусвязности. Полученный граф <mathtex>T</mathtex> называют '''графом компонент реберной двусвязности''' графа <mathtex>G</mathtex>.

В определениях, приведенных выше, <mathtex>T</mathtex> - дерево.

''а)'' <mathtex>T</mathtex> - связно. (Следует из определения)

''б)'' В <mathtex>T</mathtex> нет циклов.Пусть какие-то две последовательные вершины <mathtex>A_k</mathtex> и <mathtex>A_l</mathtex> принадлежат какому-то циклу. Тогда ребро <mathtex>(A_k, A_l)</mathtex> принадлежит этому же циклу.

Следовательно, <math>\exist</math> существуют два реберно не пересекающихся пути между вершинами <mathtex>A_k</mathtex> и <mathtex>A_l</mathtex>, т.е. <mathtex>(A_k, A_l)</mathtex> - не является мостом. Но <mathtex>(A_k, A_l)</mathtex> - мост по условию. Получили противоречие.<mathtex>T</mathtex> - дерево.