最大フロー最小カット定理
Νの最大フローとは、Νのフローのうち流量が最大のものをいい、最小カットとは、Νのカットのうち容量が最小のものをいう。このとき、最大フロー fmax と 最小カット (S, T)minについて、
| f m a x | = c ( ( S , T ) m i n ) {\displaystyle |f_{\mathrm {max} }|=c((S,T)_{\mathrm {min} })}
が成り立つ。
この定理は1956年、P. Elias、A. Feinstein、クロード・シャノンによって証明された。また、L.R. Ford, Jr. と D.R. Fulkerson も同じ年に独自に証明した。最大フローを求める問題は線形計画問題の特殊形式であり、最大フロー最小カット定理は線形計画の双対性定理の特殊ケースと見ることもできる。