Combinatorics Trees, paths, cycles, connectivity Theorem

Max-flow min-cut theorem

Statement

Let $D = (V, E)$ be a finite directed graph with distinct vertices $s$ (the source) and $t$ (the sink), and let $c \colon E \to [0, \infty)$ be a capacity function. A flow is a function $f \colon E \to \R$ such that:

$0 \le f(e) \le c(e)$ for every edge $e$ .
For every vertex $w \ne s, t$ , the total of $f$ on edges entering $w$ equals the total of $f$ on edges leaving $w$ .

The value of $f$ is the total of $f$ on edges leaving $s$ minus the total of $f$ on edges entering $s$ . An $s$ – $t$ cut is a partition $V = S \cup T$ with $s \in S$ and $t \in T$ . Its capacity is the sum of $c(e)$ over the edges $e$ from a vertex of $S$ to a vertex of $T$ . Then the maximum value of a flow exists and equals the minimum capacity of an $s$ – $t$ cut.

Remarks

Let $f$ be a flow and $(S, T)$ a cut. The value of $f$ equals the flow from $S$ to $T$ minus the flow back, so it is at most the capacity of the cut. For the reverse inequality, take a flow of maximum value and let $S$ be the set of vertices reachable from $s$ by an augmenting path. Then $t \notin S$ , every edge out of $S$ is full and every edge into $S$ carries no flow, so the cut $(S, V \setminus S)$ has capacity equal to the value. The Ford–Fulkerson method pushes flow along augmenting paths, one at a time. When all capacities are integers, it stops after finitely many steps with a maximum flow. If all capacities are integers, there is a maximum flow with integer values on all edges. This integrality gives Menger's theorem and Kőnig's theorem as special cases. The theorem is also an instance of linear programming duality.

Going deeper

For a student

The theorem is the central result about flow networks. Its proof gives an algorithm and a certificate: a maximum flow and a minimum cut prove each other optimal. Many combinatorial min-max theorems, such as Menger's theorem, Kőnig's theorem and Hall's marriage theorem, follow by building a suitable network with capacities $0$ and $1$ .

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Directed graph definition
Max-flow min-cut theorem statement

Tag	`4HMR4KQ01T`
URI	`m2://4HMR4KQ01T`
Kind	statement, theorem
Writing	W0 stub
MSC	05C21, 90B10, 90C35
Status	This copy of the site has no build data. Run `m2 status 4HMR4KQ01T`.
Uses	Directed graph
Same as	Wikidata Q608294 Wikipedia Max-flow min-cut theorem
Changed	2 November 2026