最大フロー最小カット定理
次に c ( ( S , T ) m i n ) ≥ | f m a x | {\displaystyle c((S,T)_{\mathrm {min} })\geq |f_{\mathrm {max} }|} も成り立つことをみる。任意のフロー f に対して、T へ流れこむエッジ (u, v) の流量は最大で c(u, v) であり、これの和は (S, T) のカットの容量の定義そのものである。一方、T から S へ逆流するエッジの流量は、当然ながら最小値は 0 以上である。フローの流量は流量保存により、T に流入する流量から逆流する流量を引いたものであることを確認したが、このことよりfの流量は最大で カット (S, T) の容量となる。このことより、 c ( S , T ) ≥ | f | {\displaystyle c(S,T)\geq |f|} 、特に c ( ( S , T ) m i n ) ≥ | f m a x | {\displaystyle c((S,T)_{\mathrm {min} })\geq |f_{\mathrm {max} }|} である。
証明は、以下のようにしてできる。
最大フローはフォード・ファルカーソンのアルゴリズムにより、以下のようにして見つけることができる。
二端子フローネットワーク Ν (G(V, E), c, s, t) が与えられたとする。
最大フローを見つけるために、s から t への道を見つける。この道を構成するすべてのエッジの容量の最小値を、エッジの流量として割り当てると、これはこのネットワークのフローになる。
流量の余裕を容量とする順方向のエッジと、現在の流量を容量とする逆方向のエッジからなるネットワークで、容量が 0 となるエッジを取り除いたものを残余ネットワーク (residual network) もしくは補助ネットワークと呼ぶ。この残余ネットワークの中で、同じように道を見つける。道の構成要素のうち、順方向のエッジでは流量を増加させ、逆方向のエッジでは流量を減少させることで、より流量の大きな新しいフローを得ることができる。(このような、フロー f の残余ネットワークにおける s から t への道を、f の増加道と呼ぶ。)
増加道がなくなれば、このフローが Ν の最大フローである。