Изменения
Изящное доказательство из Харари
{{ЛеммаТеорема|about=Теорема Менгера для k связности|statement=xНаименьшее число вершин, y разделяющих две несмежные вершины Gs и t, равно наибольшему числу непересекающихся простых (s-t) цепей|proof=Очевидно, что если k вершин разделяют s и t, то сущесвует не более k непересекающихся простых (s-t) цепей.Теперь покажем, что k вершин графа разделяют s и t, существует k вершинно непересекающихся пути из x в yпростых (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.б{{Утверждение|statement=Из определения 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|statement=в графе G нет вершин, смежных одновременно с s и t
|proof=
}}
{{ТеоремаУтверждение|about=II
|statement=
|proof=
}}Пусть<math>P={s, u_1, существует лишь u_2 ... t}</math> - кратчайшая (s-t) цепь в G, <math>u_1u_2=x</math> Заметим, что из(I) <math>m u_1 < k> t</math> вершинно непересекающихся путейОбразуем множество <math>S(x)={v_1, . Тогда все остальные пути будут пересекать эти m.. , v_{h-1}}</math>, причем по лемме можно удалить разделяющее в <math>l \le mG-x</math> вершин так, чтобы разорвать все добавленные пути вершины s и l из выбранных изначально.t. Тогда удалив m вершин Из (l и по одной из оставшихся I) следует, что <math>m - lu_1t \notin G</math> путейИспользуя (II) мы разорвем все пути из и беря <math>W=S(x )\cup {u_1}</math>, получаем <math>\forall i sv_i \in G</math> Таким образом в yсилу (I) <math>\forall v_it \notin G</math>. Однако, по условию необходимо удалить k вершин, чтобы граф потерял связность. Значит, предположение неверно. Прямое следствие доказано.Докажем обратное:Между если выбрать <math>W=S(x и y существует k вершинно неперескающихся путей) \cup {u_2}</math>, очевидно, нельзя удалить то в силу (II) получим <math>m < ksu_2 \in G</math> вершин так, чтобы граф потерял связностьчто противоречит выбору P как кратчайшей (s-t) цепи. ПокажемИз полученного противоречия следует, что достаточно удалить k вершинграфа G, чтобы граф потерял связность. Возьмем все пути из x в yудовлетворяющего указанным условиям не существует, они пересекут выбранные k, причем по лемме можно выбрать а значит не более k точек пересечения. Удалив все вершины пересечения существует и произвольные вершины из оставшихся путей (всего графа F, для которого теорема не более k) мы порвем все пути. Теорема доказана.верна
}}
{{Теорема
|about=
Теорема Менгера для k связности (альтернативная формулировка)
|statement=
Две несмежные вершины k-отделимы тогда и только тогда, когда они k-соединимы
}}
{{Теорема
|about=
Теорема Менгера для k-реберной связности
|statement=
Пусть G - конечный, неориентированный граф, <math>\lambda(G) = k</math> <math>\Leftrightarrow</math> для всех пар вершин <math>x, y \backepsilon G</math> существует k реберно непересекающихся путей из x в y
