Изменения

Пусть <tex>W</tex> - произвольный набор <tex>h</tex> вершин, разделяющих <tex>s</tex> и <tex>t</tex> в <tex>G</tex>. Цепь, соединяющую s с некоторой вершиной <tex>w_i \in W</tex> и не содержащую других вершин из W будем называть <tex>(s-W)</tex> цепью. Аналогично назовем <tex>(W-t)</tex> цепь. Обозначим наборы всех <tex>(s-W)</tex> и <tex>(W-t)</tex> цепей <tex>P_s</tex> и <tex>P_t</tex> соответственно.Тогда каждая <tex>(s-t)</tex> цепь начинается с элемента из <tex>P_s</tex> и заканчивается элементом из <tex>P_t</tex>, поскольку любая цепь содержит вершину из <tex>W</tex>. Общие вершины цепей из <tex>P_s</tex> и <tex>P_t</tex> принадлежат набору <tex>W</tex>, так как по крайней мере одна цепь из каждого набора <tex>P_s</tex> и <tex>P_t</tex> содержит (любую) вершину <tex>w_i</tex>, и если бы существовала некоторая вершина, не принадлежащая набору <tex>W</tex>, но содержащаяся сразу и в <tex>(s-W)</tex> и в <tex>(W-t)</tex> цепи, то нашлась бы <tex>(s-t)</tex> цепь, не имеющая вершин из <tex>W</tex>. Наконец, выполняется либо равенство <tex>P_s-W={s}</tex>, либо равенство <tex>P_t - W={t}</tex>, поскольку в противном случае либо <tex>P_s</tex> вместе с ребрами <mathtex>\{w_1t,w_2t...\}</mathtex>, либо <mathtex>P_t</mathtex> вместе с ребрами <mathtex>\{sw_1,sw_2...\}</mathtex> образуют связные графы с меньшим числом вершин, чем у <tex>G</tex>, в которых <tex>s </tex> и <tex>t </tex> не смежны, и, следовательно, в каждом из них имеется <tex>h </tex> непересекающихся <tex>(s-t) </tex> цепей. Объединяя <tex>(s-W) </tex> и <tex>(W-t) </tex> части этих цепей, образуем в графе <tex>G </tex> <tex>h </tex> непересекающихся <tex>(s-t) </tex> цепей. Мы пришли к противоречию. Утверждение доказано.

Пусть <mathtex>P=\{s, u_1, u_2 ... t\}</mathtex> - кратчайшая <tex>(s-t) </tex> цепь в <tex>G</tex>, <mathtex>u_1u_2=x</mathtex> Заметим, что из(I) <mathtex>u_1 <> \neq t</mathtex> Образуем множество <mathtex>S(x)=\{v_1, ... , v_{h-1}\}</mathtex>, разделяющее в <mathtex>G-x</mathtex> вершины <tex>s </tex> и <tex>t</tex>. Из (I) следует, что <mathtex>u_1t \notin G</mathtex> Используя (II) и беря <mathtex>W=S(x)\cup {u_1}</mathtex>, получаем <mathtex>\forall i sv_i \in G</mathtex> Таким образом в силу (I) <mathtex>\forall v_it \notin G</mathtex>. Однако, если выбрать <mathtex>W=S(x) \cup {u_2}</mathtex>, то в силу (II) получим <mathtex>su_2 \in G</mathtex>, что противоречит выбору <tex>P </tex> как кратчайшей <tex>(s-t) </tex> цепи. Из полученного противоречия следует, что графа <tex>G</tex>, удовлетворяющего указанным условиям не существует, а значит не существует и графа <tex>F</tex>, для которого теорема не верна

Теорема Менгера для <tex>k </tex> связности (альтернативная формулировка)

Две несмежные вершины k-отделимы тогда и только тогда, когда они <tex>k</tex>-соединимы

Теорема Менгера для <tex>k</tex>-реберной связности

Пусть <tex>G </tex> - конечный, неориентированный граф, <mathtex>\lambda(G) = k</mathtex> <mathtex>\Leftrightarrow</mathtex> для всех пар вершин <mathtex>x, y \in G</mathtex> существует <tex>k </tex> реберно непересекающихся путей из <tex>x </tex> в <tex>y</tex>