Изменения
несколько исправлений
{{Определение
|definition=
Множество S вершин, ребер или вершин и ребер разделяет u и v, если u и v принадлежат различным компонентам графа <math>G-S</math>
}}
Очевидно, что если k вершин разделяют s и t, то сущесвует не более k непересекающихся простых (s-t) цепей.
Теперь покажем, что если k вершин графа разделяют s и t, то существует k непересекающихся простых (s-t) цепей. Для k=1 это очевидно.
Пусть, для некоторого <math>k>1</math> это неверно. Возьмем h - наименьшее такое k и F - граф с наименьшим числом вершин, для которого при выбранном h теорема не верна. Будем удалять из F ребра, пока не получим G такой, что в G s и t разделяют h вершин, а в <math>G-x</math> <math>h-1</math> вершина, где x - произвольное ребро графа G.
Из определения G следует, что для всякого его ребра x существует множество <math>S(x)</math> из <math>h-1</math> вершин, которое в <math>G-x</math> разделяет s и t. Далее, граф <math>G-S(x)</math> содержит по крайней мере одну (s-t) цепь, так как граф G имеет h вершин, разделяющих s и t в G. Каждая такая (s-t) цепь должна содержать ребро <math>x=uv</math>, поскольку она не является цепью в <math>G-x</math>. Поэтому <math>u,v \notin S(x)</math>, и если <math>u <> s,t </math> то <math>S(x) \cup {u}</math> разделяет s и t в G {Утверждение{Лемма
|about=
I
}}
{{УтверждениеЛемма
|about=
II
Теорема Менгера для k-реберной связности
|statement=
Пусть G - конечный, неориентированный граф, <math>\lambda(G) = k</math> <math>\Leftrightarrow</math> для всех пар вершин <math>x, y \backepsilon in G</math> существует k реберно непересекающихся путей из x в y
|proof=
Аналогично вершинному случаютеореме для вершинной связности.
}}
