Изменения

Пусть <tex> G </tex> {{- --}} связный граф.

(1) '''Мост ''' графа <tex>G</tex> {{- --}} ребро, соединяющее две компоненты реберной двусвязности <tex>G</tex>.

(2) Мост графа <tex>G</tex> {{- --}} ребро, при удалении которого граф <tex>G</tex> становится несвязным.

<tex>(1) \Rightarrow (2)</tex> Пусть ребро <tex>x</tex> соединяет вершины <tex>a</tex> и <tex>b</tex>. Пусть граф <tex> G - {x} </tex> {{- --}} связный. Тогда между вершинами <tex>a</tex> и <tex>b</tex> существует еще один путь, т.е. между вершинами <tex>a</tex> и <tex>b</tex> существуют два реберно-непересекающихся пути. Но тогда ребро <tex>x</tex> не является мостом графа <tex>G</tex>. Противоречие.

<tex>(2) \Rightarrow (4)</tex> В условиях определения (4) пусть существует такие вершины <tex>u</tex> и <tex>w</tex>, что между ними существует простой путь <tex>P: x \notin P</tex>. Но тогда граф <tex>G - {x}</tex> {{- --}} связный. Противоречие.