[proofplan] The proof has two parts. The weak direction — every feasible flow value is at most every cut capacity — follows from a direct counting argument. The strong direction constructs a cut achieving equality with the maximum flow. Starting from an optimal flow $x^*$, we define the set $S$ of all nodes reachable from the source via augmenting paths in the residual graph. Since the flow is optimal, no augmenting path reaches the sink, so $S$ is a valid source-side cut. We then show that every forward edge across the cut is saturated and every backward edge carries zero flow, forcing the flow value to equal the cut capacity. [/proofplan] [step:Establish the weak inequality: every flow value is at most every cut capacity] Let $x$ be any feasible flow with value $\delta$, and let $S \subset V$ be any cut with $1 \in S$ and $n \in V \setminus S$. Define the flow across the cut: \begin{align*} f_x(S, V \setminus S) &:= \sum_{\substack{(i,j) \in E \\ i \in S, \, j \notin S}} x_{ij}, \qquad f_x(V \setminus S, S) := \sum_{\substack{(i,j) \in E \\ i \notin S, \, j \in S}} x_{ij}. \end{align*} By flow conservation, the net flow out of $S$ equals the flow value: \begin{align*} \delta = f_x(S, V \setminus S) - f_x(V \setminus S, S). \end{align*} To verify this, sum the flow conservation equations over all nodes $i \in S$. Each edge entirely within $S$ contributes equally to the outflow of its tail and the inflow of its head, so it cancels. The remaining terms are exactly the flow across the cut. The source node $1 \in S$ contributes $+\delta$ (by definition of the flow value), and all other nodes in $S$ contribute $0$ (by conservation). Since $x_{ij} \geq 0$ for all edges, we have $f_x(V \setminus S, S) \geq 0$, so: \begin{align*} \delta = f_x(S, V \setminus S) - f_x(V \setminus S, S) \leq f_x(S, V \setminus S) \leq \sum_{\substack{(i,j) \in E \\ i \in S, \, j \notin S}} C_{ij} = C(S), \end{align*} where the last inequality uses $x_{ij} \leq C_{ij}$ (the capacity constraint). Therefore $\delta \leq C(S)$ for every feasible flow $\delta$ and every cut $S$. [guided] The weak inequality $\delta \leq C(S)$ is the easy direction and holds for any flow-cut pair. The argument is a "bottleneck" observation: all flow from source to sink must cross the cut, so the flow value cannot exceed the total capacity across the cut. The formal verification uses the "summing trick": sum the flow conservation equations $\sum_{j:(i,j) \in E} x_{ij} - \sum_{j:(j,i) \in E} x_{ji} = b_i$ over all $i \in S$, where $b_1 = \delta$ (the source produces $\delta$ units), $b_n = -\delta$ (the sink absorbs $\delta$ units, but $n \notin S$), and $b_i = 0$ for all other nodes. Internal edges (both endpoints in $S$) cancel in the sum: \begin{align*} \sum_{i \in S} b_i = \sum_{i \in S} \Bigl(\sum_{j:(i,j) \in E} x_{ij} - \sum_{j:(j,i) \in E} x_{ji}\Bigr) = f_x(S, V \setminus S) - f_x(V \setminus S, S). \end{align*} Since $1 \in S$ and $n \notin S$, we have $\sum_{i \in S} b_i = \delta$. The two inequalities $f_x(V \setminus S, S) \geq 0$ and $f_x(S, V \setminus S) \leq C(S)$ then give $\delta \leq C(S)$. [/guided] [/step] [step:Define the residual graph and augmenting paths] Given a feasible flow $x$, define the **residual graph** $G_x = (V, E_x)$ where $E_x$ consists of: - **Forward edges**: $(i,j) \in E_x$ whenever $(i,j) \in E$ and $x_{ij} < C_{ij}$ (there is residual capacity $C_{ij} - x_{ij} > 0$). - **Backward edges**: $(j,i) \in E_x$ whenever $(i,j) \in E$ and $x_{ij} > 0$ (the flow $x_{ij}$ can be reduced). An **augmenting path** from the source $1$ to the sink $n$ is a path in $G_x$. Along such a path, one can increase the flow value by pushing $\varepsilon > 0$ units: increase $x_{ij}$ by $\varepsilon$ on each forward edge and decrease $x_{ij}$ by $\varepsilon$ on each backward edge, where $\varepsilon$ is the minimum residual capacity along the path. [guided] The residual graph encodes all the ways the current flow can be modified while maintaining feasibility. A forward edge $(i,j)$ in the residual graph means we can push more flow along $(i,j)$ in the original network (up to the remaining capacity $C_{ij} - x_{ij}$). A backward edge $(j,i)$ in the residual graph means we can "undo" some of the flow currently going from $i$ to $j$ (by reducing $x_{ij}$). An augmenting path in $G_x$ from source to sink gives a recipe for strictly increasing the total flow value. If $\varepsilon = \min\{\text{residual capacities along the path}\} > 0$, then adjusting the flow by $\varepsilon$ along the path produces a new feasible flow with value $\delta + \varepsilon > \delta$. The contrapositive is crucial: if the flow is optimal (no flow of higher value exists), then no augmenting path from source to sink can exist in $G_x$. [/guided] [/step] [step:Construct the minimum cut from an optimal flow] Let $x^*$ be an optimal flow with value $\delta^*$. Since $x^*$ is optimal, no augmenting path from $1$ to $n$ exists in the residual graph $G_{x^*}$ (otherwise the flow value could be increased, contradicting optimality). Define: \begin{align*} S := \{i \in V : \text{there exists a path from } 1 \text{ to } i \text{ in } G_{x^*}\}. \end{align*} Since the source $1$ is reachable from itself (via the empty path), $1 \in S$. Since no augmenting path reaches the sink, $n \notin S$. Therefore $S$ is a valid cut separating the source from the sink. [guided] The set $S$ consists of all nodes reachable from the source in the residual graph. This is the key construction: the absence of augmenting paths means the sink $n$ is not reachable, so $n \in V \setminus S$ and $(S, V \setminus S)$ is a legitimate $s$-$t$ cut. We will show that this particular cut has capacity exactly equal to $\delta^*$, which combined with the weak inequality $\delta^* \leq C(S)$ forces equality and establishes the max-flow min-cut theorem. [/guided] [/step] [step:Show that all forward edges across the cut are saturated] Consider any edge $(u, w) \in E$ with $u \in S$ and $w \in V \setminus S$ (a forward edge across the cut). [claim:Forward edges across the cut carry flow equal to capacity] For every $(u, w) \in E$ with $u \in S$ and $w \notin S$, we have $x^*_{uw} = C_{uw}$. [/claim] [proof] Suppose for contradiction that $x^*_{uw} < C_{uw}$. Then $(u, w)$ is a forward edge in the residual graph $G_{x^*}$, meaning $w$ is reachable from $u$ in $G_{x^*}$. Since $u \in S$, there is a path from $1$ to $u$ in $G_{x^*}$. Extending this path by the edge $(u, w)$ gives a path from $1$ to $w$ in $G_{x^*}$, so $w \in S$. This contradicts $w \notin S$. [/proof] Therefore $f_{x^*}(S, V \setminus S) = \sum_{\substack{(u,w) \in E \\ u \in S, w \notin S}} x^*_{uw} = \sum_{\substack{(u,w) \in E \\ u \in S, w \notin S}} C_{uw} = C(S)$. [guided] The argument is by contradiction and uses the definition of $S$. If some forward edge $(u,w)$ crossing the cut were not saturated, the residual graph would contain this edge, making $w$ reachable from $1$ (via the path to $u$ followed by the edge to $w$). But $w \notin S$ means $w$ is not reachable — contradiction. This is the core of the max-flow min-cut argument: optimality of the flow (no augmenting paths) forces every forward edge across the constructed cut to be at full capacity. [/guided] [/step] [step:Show that all backward edges across the cut carry zero flow] [claim:Backward edges into the cut carry zero flow] For every $(w, u) \in E$ with $w \notin S$ and $u \in S$, we have $x^*_{wu} = 0$. [/claim] [proof] Suppose for contradiction that $x^*_{wu} > 0$. Then $(u, w)$ is a backward edge in the residual graph $G_{x^*}$ (we can reduce flow on $(w, u)$ by rerouting through $u$). Since $u \in S$, there is a path from $1$ to $u$ in $G_{x^*}$. Extending by the backward edge $(u, w)$ gives a path from $1$ to $w$ in $G_{x^*}$, so $w \in S$. This contradicts $w \notin S$. [/proof] Therefore $f_{x^*}(V \setminus S, S) = \sum_{\substack{(w,u) \in E \\ w \notin S, u \in S}} x^*_{wu} = 0$. [guided] The same reachability argument applies to backward edges. If some edge $(w, u)$ with $w \notin S$ and $u \in S$ carried positive flow, then the residual graph would contain the reverse edge $(u, w)$ (representing the possibility of reducing $x^*_{wu}$). This would make $w$ reachable from $1$, contradicting $w \notin S$. The two claims together — all forward edges saturated, all backward edges empty — completely characterise the flow across the cut $S$. [/guided] [/step] [step:Conclude the max-flow min-cut equality] From the weak inequality step, the net flow across any cut equals the flow value: \begin{align*} \delta^* = f_{x^*}(S, V \setminus S) - f_{x^*}(V \setminus S, S). \end{align*} Substituting the results of the two claims: \begin{align*} \delta^* = C(S) - 0 = C(S). \end{align*} We have exhibited a cut $S$ with $C(S) = \delta^*$. Combined with the weak inequality $\delta^* \leq C(S')$ for every cut $S'$, this gives: \begin{align*} \delta^* = C(S) \geq \min_{S'} C(S') \geq \delta^*, \end{align*} so equality holds throughout: \begin{align*} \delta^* = \min\{C(S') : S' \subset V, \; 1 \in S', \; n \notin S'\}. \end{align*} The maximum flow value equals the minimum cut capacity. [guided] The proof combines two ingredients: 1. **Weak duality** (from the first step): $\delta \leq C(S')$ for every flow $\delta$ and every cut $S'$. Taking the maximum over flows and minimum over cuts: $\max \delta \leq \min C(S')$. 2. **Existence of an achieving pair** (from the construction): we found a specific flow $x^*$ and a specific cut $S$ with $\delta^* = C(S)$. This forces $\max \delta = \min C(S')$. The overall structure mirrors LP strong duality: weak duality gives one inequality, and exhibiting a primal-dual pair achieving equality gives the reverse. Indeed, the max-flow min-cut theorem can be proved directly from LP strong duality applied to the max-flow LP and its dual. The augmenting-path proof given here makes the construction explicit and provides the algorithmic insight that the Ford-Fulkerson method terminates when (and only when) the residual graph separates source from sink. [/guided] [/step]