Изменения

Пусть <tex>W</tex> - произвольный набор <tex>h</tex> вершин, разделяющих <tex>s</tex> и <tex>t</tex> в <tex>G</tex>. Цепь, соединяющую <tex>s </tex> с некоторой вершиной <tex>w_i \in W</tex> и не содержащую других вершин из <tex>W </tex> будем называть <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> вместе с ребрами <tex>\{w_1t,w_2t...\}</tex>, либо <tex>P_t</tex> вместе с ребрами <tex>\{sw_1,sw_2...\}</tex> образуют связные графы с меньшим числом вершин, чем у <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> цепей. Мы пришли к противоречию. Утверждение доказано.

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