Для любой сети G=(J, U) с одним источником S и одним стоком t величина максимального потока из S в t равна пропускной способности минимального разреза, отделяющего S от t.

Дугу, входящею в некоторую цепь в сети, будем наз. прямой, если ее направление совпадает с направлением обхода вершин, и обратной – в противном случае.

Дуга (i, j) насыщена потоком, если X_ij=C_ij.

Доказательство:

Пусть V^* величина максим. потока в даной сети. Необходимо доказать, что можно построить такой разрез , для которого C=V. Определим множество вершин R^* по следующему правилу:

Вершины, принадлежащие множеству R^* согласно правилу (1) определяется одна за другой. Вершина j включает в в множество R^* , если дуга (i, j) не насыщена потоком, или если поток по обратной дуге (j, i) явл. положительным. Покажем что применяя правило (1) вершина t не будет принадлежать R^* , т. е. .

Пусть , тогда существует некоторая цепь (i₁, i_{2 …} i_m), для которой i₁=S, i_m=t и прямые дуги этой цепи (i_к, i_к+1) не насыщены потоком т. е. X_{ik ik+1}<C_{ik ik+1} , а поток на обратных дугах положителен т. е. X_ik+1,i_k>0. Найдем минимальное значение потока на всех прямых дугах.

min(X_ik+1i_k)=E₁

и минимальное значение потока на обратных дугах:

min(X_ik+1i_k)=E₂

и обозначим min (E_1, E₂)=E

Тогда поток в сети (на рассмотренной цепи) можно увеличить на Е и поток в сети будет: V^*+E . Получим противоречие тому что V^* — максимальный поток. А следовательно , т. е. построен разрез .