最大フロー最小カット定理
右図はノード V = { s , o , p , q , r , t } {\displaystyle V=\{s,o,p,q,r,t\}} からなるネットワークであり、始点 s {\displaystyle s} から 終点 t {\displaystyle t} への総流量は 5 で、これがこのネットワークの最大である。
このネットワークには3つの最小カットが存在する。

( o , q ) {\displaystyle (o,q)} と ( r , t ) {\displaystyle (r,t)} が飽和しているにもかかわらず、 S = { s , o , p , r } , T = { q , t } {\displaystyle S=\{s,o,p,r\},T=\{q,t\}} は最小カットではないことに注意されたい。これは残余ネットワーク(residual network) G f {\displaystyle G_{f}} において、エッジ (r,q) の容量が c f ( r , q ) = c ( r , q ) − f ( r , q ) = 0 − ( − 1 ) = 1 {\displaystyle c_{f}(r,q)=c(r,q)-f(r,q)=0-(-1)=1} であるためである。
二端子フローネットワーク N = ( G ( V , E ) , c , s , t ) {\displaystyle {\boldsymbol {\mathrm {N} }}=(G(V,E),c,s,t)} が与えられたとする。つまり、有限の有向グラフ G ( V , E ) {\displaystyle G(V,E)} の各エッジ(辺) ( u , v ) {\displaystyle (u,v)} に非負実数の容量 c ( u , v ) {\displaystyle c(u,v)} が割り当てられており、始点となるノード(入口) s {\displaystyle s} と、終点となるノード(出口) t {\displaystyle t} が指定されたとする。
フロー f の流量 | f | とは、入口 s から出て行くフローの合計である。
| f | = ∑ v ∈ N − ( s ) f ( s , v ) {\displaystyle |f|=\sum _{v\in N^{-}(s)}f(s,v)}
最大フローの残余ネットワークは、 s {\displaystyle s} から到達可能なノード群 S {\displaystyle S} と到達不可能なノード群 T {\displaystyle T} に分けることができる。増加道がないので、t は T に含まれる。定義より、残余ネットワーク上では S から T へのエッジは存在しない。もとのネットワークに戻って考えると、S から出るエッジ (u, v) はすべて、残余ネットワークに存在しないことから、流量の余裕がない、すなわち f ( u , v ) = c ( u , v ) {\displaystyle f(u,v)=c(u,v)} となっていることが分かる。また、S に入るエッジは逆方向のエッジが残余ネットワークにないことから、流量が 0 であることが分かる。これらのことより、 c ( S , T ) = | f m a x | {\displaystyle c(S,T)=|f_{\mathrm {max} }|} となる。
したがって、 | f m a x | = c ( S , T ) ≥ c ( ( S , T ) m i n ) {\displaystyle |f_{\mathrm {max} }|=c(S,T)\geq c((S,T)_{\mathrm {min} })} といえる。