Network Flows and Max-Flow Min-Cut

Flow networks underlie bipartite matching algorithms: constructing a unit-capacity bipartite flow network and computing max flow gives the maximum matching size directly, recovering König's theorem and Hall's marriage theorem as special cases. In connectivity theory, setting all capacities to $1$ (or to vertex-splitting gadgets) and computing max flow between two vertices computes the maximum number of edge- (or vertex-) disjoint paths between them, which is precisely the content of Menger's Theorem — the natural next theorem in this circle of ideas, connecting flows back to Vertex and Edge Connectivity. In computer vision, min-cut/max-flow algorithms solve binary image segmentation (foreground/background) by modeling pixel similarity as edge capacities, an approach popularized by Boykov and Jolly. In operations research and scheduling, project selection problems with prerequisite and profit structures reduce to min-cut computations (the "closure problem"). In statistical physics, the max-flow min-cut duality is closely related to computing ground states of certain random-field Ising models via graph cuts. In cryptography and network reliability, min-cut values quantify the minimum number of compromised links needed to disconnect a network, directly informing robustness metrics. In circuit design and VLSI routing, flow techniques bound achievable wire routing capacity between terminal regions.

Ask the tutor: How does the max-flow min-cut theorem's proof structure directly yield Menger's theorem on disjoint paths?

Picture the network as a system of one-way pipes, with $s$ a pump station and $t$ a reservoir. Water flows along edges, each pipe has a maximum throughput given by its capacity, and at every intermediate junction whatever flows in must flow out — no water is created, destroyed, or stored anywhere except at $s$ (production) and $t$ (consumption). The value of the flow is the total rate at which water leaves the pump. Now imagine trying to sabotage this system by cutting a set of pipes so that no water can possibly get from $s$ to $t$. A cut $(S,T)$ corresponds to grouping junctions into "source side" $S$ and "sink side" $T$; to physically disconnect $s$ from $t$ you must sever every pipe running from $S$ into $T$ (pipes running backward from $T$ into $S$ do not need to be touched, since water is not trying to flow that way). The capacity of the cut is the total bandwidth you must destroy. Intuitively, no flow can ever exceed the capacity of any single cut, because every unit of flow that reaches $t$ must, at some point, cross from the $S$-side to the $T$-side of that cut. The深 theorem asserts something stronger and non-obvious: not only is max-flow bounded by every cut, it is achieved by the tightest possible cut — there is no gap.

The proof of the max-flow min-cut theorem is built on the notion of a residual graph, which records how much more flow can still be pushed along, or canceled back along, each edge.

The term $c(u,v) - f(u,v)$ is the leftover forward capacity on edge $(u,v)$; the term $f(v,u)$ is the amount of flow on the reverse edge that could be "undone" by pushing flow the other way. Both contribute usable residual capacity.

Example 1: a network with an asymmetric structure and a bottleneck cut. Let $G$ have vertices $\{s,a,b,c,t\}$ and directed edges with capacities:

Iteration 1. Start with $f \equiv 0$. Residual graph equals $G$ itself. Choose augmenting path $s \to a \to c \to t$. Bottleneck $= \min(9,6,10) = 6$. Push $6$: now

Iteration 2. Residual capacities: $c_f(s,a)=3$, $c_f(a,c) = 0$ (saturated, but reverse edge $c_f(c,a)=6$ now exists), $c_f(c,t)=4$, all others unchanged from $G$. Choose path $s \to b \to t$. Bottleneck $=\min(8,6)=6$. Push $6$: now

Iteration 3. Residual capacities now: $c_f(s,a)=3$, $c_f(s,b)=2$, $c_f(b,t) = 0$ (saturated; reverse $c_f(t,b)=6$), $c_f(a,c)=0$ (reverse $c_f(c,a)=6$), $c_f(c,t)=4$, $c_f(a,b)=2$, $c_f(b,c)=1$. Try path $s \to a \to b \to c \to t$: capacities along it are $3, 2, 1, 4$; bottleneck $=1$. Push $1$: update

Iteration 4. Residual capacities: $c_f(s,a) = 2$, $c_f(s,b)=2$, $c_f(a,b) = 1$ (net so far $1$, capacity $2$), $c_f(b,c) = 0$ (saturated; reverse $c_f(c,b) = 1$), $c_f(a,c) = 0$ still (reverse $c_f(c,a)=6$), $c_f(c,t) = 3$, $c_f(b,t)=0$ (reverse $c_f(t,b)=6$). Is there still an augmenting path? From $s$ we can reach $a$ (via $c_f(s,a)=2$) and $b$ (via $c_f(s,b)=2$ and via $a\to b$). From $a$, edges available: $a\to b$ ($c_f=1$), reverse $a \to$ nothing else new. From $b$: $b \to c$ is saturated (0), but is there $b \to t$? No, saturated. Reverse edges from $b$: $c_f(b,a)$? That would require $f(a,b) > 0$, and indeed $f(a,b)=1>0$ so $c_f(b,a) \ge 1$— but $a$ is already reached, no new information. From $c$ (not yet reached): can we reach $c$? Only via $b \to c$ (saturated) or reverse of $c \to a$, i.e. edge $c_f(c,a)$ which goes from $c$, not to $c$ — irrelevant for reaching $c$. Also reverse of $c\to t$ doesn't help reach $c$ from $S$. So $c$ is unreachable, hence $t$ is unreachable (all paths to $t$ pass through $c$ or through the saturated $b\to t$). So $S^* = \{s,a,b\}$, $T^* = \{c,t\}$. Compute $c(S^*,T^*)$: edges from $S^*$ to $T^*$ are $a\to c$ (capacity $6$) and $b \to c$ (capacity $1$); note $b \to t$ also crosses ($S^*$ to $T^*$), capacity $6$. Total:

This matches $|f|=13$ exactly, confirming by the theorem that $f$ is maximum and $(S^*,T^*)$ is a minimum cut. The bottleneck of the whole network is the combined capacity out of $\{s,a,b\}$, namely $13$, even though individual edges like $c(s,a)=9$ or $c(c,t)=10$ look larger in isolation — the theorem correctly identifies the global obstruction, not any single edge.

Example 2: using a residual back-edge to correct an earlier greedy choice. Take vertices $\{s,x,y,t\}$ with edges

Iteration 1. Greedily augment along $s\to x \to t$ with bottleneck $\min(10,4) = 4$. Set $f(s,x)=4, f(x,t)=4$, $|f|=4$. Iteration 2. Augment along $s \to y \to t$, bottleneck $\min(10,9)=9$. Set $f(s,y)=9, f(y,t)=9$, $|f| = 13$. Iteration 3. Residual graph: $c_f(s,x) = 6$, $c_f(s,y)=1$, $c_f(x,y) = 2$ (untouched), $c_f(x,t) = 0$ (saturated; reverse $c_f(t,x) = 4$), $c_f(y,t) = 0$ (saturated; reverse $c_f(t,y)=9$). Also reverse residuals $c_f(x,s) = 4$, $c_f(y,s) = 9$ exist but point the wrong way for reaching $t$. Path attempt: $s \to x \to y \to \cdots$? Edge $x\to y$ has residual capacity $2 > 0$. From $y$, forward to $t$ is saturated (residual $0$). From $y$, is there anywhere else? $y \to s$ (reverse of $s\to y$) doesn't help. So this branch dead-ends at $y$ without reaching $t$. Check all reachability from $s$ carefully: $s\to x$ (residual 6), $s \to y$ (residual 1), $x \to y$ (residual 2). So reachable set is $\{s,x,y\}$. From $x$: only $x\to y$ available (since $x\to t$ saturated). From $y$: nothing forward-usable reaches $t$ (saturated), and $y\to s$ is not useful. So $t$ is unreachable: $S^* = \{s,x,y\}$, $T^* = \{t\}$.

Max flow is $13$, matching the min cut exactly, and note the edge $x\to y$ (capacity $2$) was never used in the final flow, illustrating that not every edge need carry flow in an optimal solution — its potential role was superseded once $x\to t$ and $y \to t$ were both saturated directly from $s$.