143
правки
Изменения
утверждение 2
II
|statement=
любой набор W, содержащий h вершин и разделяющий s и t является смежным с s или t
|proof=
Пусть W - произвольный набор h вершин, разделяющих s и t в G. Цепь, соединяющую s с некоторой вершиной <math>w_i \in W</math> и не содержащую других вершин из W будем называть (s-W) цепью. Аналогично назовем (W-t) цепь. Обозначим наборы всех (s-W) и (W-t) цепей <math>P_s</math> и <math>P_t</math> соответственно.Тогда каждая (s-t) цепь начинается с элемента из <math>P_s</math> и заканчивается элементом из <math>P_t</math>, поскольку любая цепь содержит вершину из W. Общие вершины цепей из <math>P_s</math> и <math>P_t</math> принадлежат набору W, так как по крайней мере одна цепь из каждого набора <math>P_s</math> и <math>P_t</math> содержит (любую) вершину <math>w_i</math>, и если бы существовала некоторая вершина, не принадлежащая набору W, но содержащаяся сразу и в (s-W) и в (W-t) цепи, то нашлась бы (s-t) цепь, не имеющая вершин из W. Наконец, выполняется либо равенство <math>P_s-W={s}</math>, либо равенство <math>P_t - W={t}</math>, поскольку в противном случае либо <math>P_s</math> вместе с ребрами <math>{w_1t,w_2t...}</math>, либо <math>P_t</math> вместе с ребрами <math>{sw_1,sw_2...}</math> образуют связные графы с меньшим числом вершин, чем у G, в которых s и t не смежны, и, следовательно, в каждом из них имеется h непересекающихся (s-t) цепей. Объединяя (s-W) и (W-t) части этих цепей, образуем в графе G h непересекающихся (s-t) цепей. Мы пришли к противоречию. Утверждение доказано.
}}
Пусть <math>P={s, u_1, u_2 ... t}</math> - кратчайшая (s-t) цепь в G, <math>u_1u_2=x</math> Заметим, что из(I) <math>u_1 <> t</math> Образуем множество <math>S(x)={v_1, ... , v_{h-1}}</math>, разделяющее в <math>G-x</math> вершины s и t. Из (I) следует, что <math>u_1t \notin G</math> Используя (II) и беря <math>W=S(x)\cup {u_1}</math>, получаем <math>\forall i sv_i \in G</math> Таким образом в силу (I) <math>\forall v_it \notin G</math>. Однако, если выбрать <math>W=S(x) \cup {u_2}</math>, то в силу (II) получим <math>su_2 \in G</math>, что противоречит выбору P как кратчайшей (s-t) цепи. Из полученного противоречия следует, что графа G, удовлетворяющего указанным условиям не существует, а значит не существует и графа F, для которого теорема не верна
