Max-flow min-cut theorem

On this page

Interactive

Augmenting paths, residual edges, and the minimum cut

AugmentAutoReset

Flow network (flow / capacity)

Augmenting pathMinimum cutFlow

Press Augment to find the first augmenting path.

max flow = min cut

Why flows and cuts meet

A flow describes how much material can be sent from a source to a sink through capacity-limited directed edges. A cut describes a bottleneck separating them. The max-flow min-cut theorem says these two views identify the same limiting quantity.

Let $G=(V,E)$ be a finite directed network with distinct source $s$ and sink $t$. Every edge $e$ has a finite, nonnegative capacity $c_e$. A feasible flow assigns $f_e$ to each edge such that

$$0\leq f_e\leq c_e,$$

and total inflow equals total outflow at every vertex other than $s$ and $t$. Its value $|f|$ is the net flow leaving $s$, equivalently the net flow entering $t$.

An $s$–$t$ cut is a partition $V=S\mathbin{\dot\cup}T$ with $s\in S$ and $t\in T$. Its capacity counts original edges directed from $S$ to $T$:

$$c(S,T)=\sum_{e=(u,v)\in E:\,u\in S,\ v\in T}c_e.$$

The theorem states that the largest feasible flow value equals the smallest $s$–$t$ cut capacity.

Every cut bounds every flow

For any feasible flow and cut, sum net outflow over vertices in $S$. Internal edges cancel, leaving

$$\begin{aligned} |f| &= \sum_{e=(u,v):\,u\in S,\,v\in T}f_e\\ &\quad-\sum_{e=(u,v):\,u\in T,\,v\in S}f_e. \end{aligned}$$

The second sum is nonnegative, while each term in the first is at most its edge capacity. Therefore $|f|\leq c(S,T)$ for every flow and every cut.

Residual reachability proves equality

A maximum flow exists: the zero flow is feasible, and the feasible flows form a closed, bounded subset of a finite-dimensional space. For each original edge $u\to v$, its residual graph has a forward arc of capacity $c_e-f_e$ and a reverse arc of capacity $f_e$. The reverse arc represents the option to cancel existing flow on that particular edge.

Let $S$ be the vertices reachable from $s$ along positive-capacity residual arcs, and let $T=V\setminus S$. The sink cannot be in $S$: a residual path to $t$ would have a positive bottleneck, allowing the flow to increase. No positive-capacity residual arc crosses from $S$ to $T$. Thus every original edge from $S$ to $T$ is saturated, and every original edge from $T$ to $S$ carries zero flow (otherwise its reverse residual arc would cross the cut). The cut identity becomes $|f|=c(S,T)$. Together with the bound above, this proves that this flow is maximum and this cut is minimum.

A small certificate

Take edges $s\to a$ of capacity 3, $s\to b$ of capacity 2, $a\to t$ of capacity 2, $a\to b$ of capacity 1, and $b\to t$ of capacity 3. Send flows $3,2,2,1,3$ on those edges, respectively. Conservation holds at $a$ and $b$, and the flow value is 5. The cut $S=\{s\}$, $T=\{a,b,t\}$ has capacity $3+2=5$. Since a flow of value 5 meets a cut of capacity 5, neither can be improved.

Takeaway: a flow is a feasible shipment, a cut is a capacity bottleneck, and residual reachability constructs a cut whose capacity certifies optimality.