最大流最小カット定理

まず弱双対性を示す。$s$ が $S$ に、$t$ が $T$ に属する任意の $s$-$t$ カット $S$,$T$ と、任意の実行可能フロー $|f|$ を考える。$s$ から出るすべての単位のフローは、最終的に $t$ に到達するために $S$ から $T$ へ渡らなければならず、保存則により、カットを横切る正味フローはフローの総量に等しい。$T$ から $S$ へ戻る辺はこの正味量を減らすことしかできないため、フロー値は $S$ から出る辺の容量の合計を決して超えない。すなわち任意のカットについて $|f|$ は $\mathrm{cap}(S,T)$ 以下である。

次にFord-Fulkersonアルゴリズムを最後まで実行する:残余グラフ(残り容量とすでに送ったフローの逆転可能分)の中で $s$ から $t$ への経路を繰り返し見つけ、その経路上で最も細い辺が許す分だけフローを押し出す。容量は整数または有理数であり、使用するたびに経路上で真に減少するため、この過程は有限回の増加で終了する。

終了時には増加経路が存在しない。最終的な残余グラフで $s$ から到達可能なノードの集合を $S$、残りを $T$ とする(到達する経路がないため、$t$ は $T$ に属する)。元のネットワークで $S$ から $T$ へのすべての辺は完全に飽和していなければならず(そうでなければ残余容量が残り、$S$ がさらに広がる)、$T$ から $S$ へのすべての辺のフローはゼロでなければならない(そうでなければその逆残余辺が $S$ を広げる)。

$S$ 内のすべてのノードについてフロー保存則を足し合わせると、総フロー値は飽和した順方向辺の容量の合計からゼロの逆方向フローを引いたものに正確に等しく、これはこのカットに対する $\mathrm{cap}(S,T)$ そのものである。最初の段落で示した上界と合わせると、このカットは達成可能な最小容量を実現しており、したがって最大フロー値は最小カット容量に等しい。