Изменения

Наименьшее число вершин, разделяющих две несмежные вершины s и t, равно наибольшему числу непересекающихся простых (s-t) цепей

|proof=

Очевидно, что если k вершин разделяют s и t, то сущесвует не более k непересекающихся простых (s-t) цепей.

I

|statement=

|proof=

Если в G есть вершина w, смежная как с s, так и с t, то в графе <math>G-w</math> для разделения s и t требуется <math>h - 1</math> непересекающихся (s-t) цепей. Добавляя w, получаем в графе G h непересекающихся (s-t) цепей, что противоречит предположению о графе F

II

|statement=

|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) цепей. Мы пришли к противоречию. Утверждение доказано.