[proofplan] We prove integrality by induction over the augmentations. Integer capacities and an integer-valued current flow imply that every residual capacity is an integer, so the bottleneck value along any augmenting path is a positive integer and augmentation preserves integrality. Since each augmentation increases the value of the flow by at least $1$, while every feasible flow is bounded above by the total capacity leaving $s$, only finitely many augmentations can occur. Finally, when no augmenting path remains, the set of vertices reachable from $s$ in the residual network determines a cut whose capacity equals the current flow value, proving maximality. [/proofplan] [step:Define residual arcs with labels so antiparallel edges remain distinct] Let $f:E \to \mathbb{R}_{\geq 0}$ be a feasible $s$-$t$ flow on $N$. Thus $0 \leq f(e) \leq c(e)$ for every $e \in E$, and for every vertex $v \in V \setminus \{s,t\}$ the conservation law holds: \begin{align*} \sum_{\{u\in V:(u,v)\in E\}} f(u,v) = \sum_{\{w\in V:(v,w)\in E\}} f(v,w). \end{align*} The value of $f$ is \begin{align*} |f| = \sum_{\{w\in V:(s,w)\in E\}} f(s,w) - \sum_{\{u\in V:(u,s)\in E\}} f(u,s). \end{align*} For every original edge $e=(u,v)\in E$, define two labelled residual arcs: the forward residual arc $a_{e,+}=(e,+)$ has tail $u$, head $v$, and residual capacity \begin{align*} r_f(a_{e,+}) := c(e)-f(e), \end{align*} and the backward residual arc $a_{e,-}=(e,-)$ has tail $v$, head $u$, and residual capacity \begin{align*} r_f(a_{e,-}) := f(e). \end{align*} The label $e$ is part of the residual arc, so if both $(u,v)$ and $(v,u)$ lie in $E$, the forward residual arc of one edge and the backward residual arc of the other edge are still distinct residual arcs. The residual network contains precisely those labelled residual arcs whose residual capacity is positive. An augmenting path is a directed path from $s$ to $t$ in this labelled residual network. If $P$ is such a path, define its bottleneck capacity by \begin{align*} \delta(P) := \min_{a \in P} r_f(a), \end{align*} where $a$ ranges over the labelled residual arcs of $P$. Since $P$ is finite and every residual arc on $P$ has positive residual capacity, $\delta(P)>0$. [/step] [step:Prove by induction that every produced flow is integer-valued] The zero flow $f_0:E \to \mathbb{Z}_{\geq 0}$ defined by $f_0(e)=0$ for every $e\in E$ is integer-valued. Assume that the current flow $f:E \to \mathbb{Z}_{\geq 0}$ is integer-valued. Since $c(e)\in \mathbb{Z}_{\geq 0}$ and $f(e)\in \mathbb{Z}_{\geq 0}$ for every $e\in E$, every forward residual capacity \begin{align*} r_f(a_{e,+})=c(e)-f(e) \end{align*} is an integer, and every backward residual capacity \begin{align*} r_f(a_{e,-})=f(e) \end{align*} is an integer. Hence for any augmenting path $P$, the bottleneck $\delta(P)$ is the minimum of finitely many positive integers, so \begin{align*} \delta(P)\in \mathbb{Z}_{>0}. \end{align*} The augmentation along $P$ replaces $f$ by the map $f':E \to \mathbb{R}_{\geq 0}$ defined edge by edge as follows. For an original edge $e\in E$, if the labelled forward residual arc $a_{e,+}$ lies on $P$, set \begin{align*} f'(e)=f(e)+\delta(P). \end{align*} If the labelled backward residual arc $a_{e,-}$ lies on $P$, set \begin{align*} f'(e)=f(e)-\delta(P). \end{align*} If neither labelled residual arc associated to $e$ lies on $P$, set \begin{align*} f'(e)=f(e). \end{align*} We may take $P$ to be a simple directed path: if a directed augmenting path contains a directed cycle, delete the cycle; every remaining residual arc was already on the original path, so the bottleneck is no smaller. For a simple directed path, both $a_{e,+}$ and $a_{e,-}$ cannot occur for the same original edge $e=(u,v)$, since this would force the path to visit $u$ and $v$ twice. Thus the displayed definition is unambiguous. The inequalities $\delta(P)\leq c(e)-f(e)$ in the forward case and $\delta(P)\leq f(e)$ in the backward case show that $0\leq f'(e)\leq c(e)$ for every $e\in E$. At each internal vertex of $P$, one incident residual arc enters and one incident residual arc leaves, so the net change in inflow equals the net change in outflow; vertices outside $P$ have no change. Hence $f'$ is again a feasible $s$-$t$ flow. Because $f(e)$ and $\delta(P)$ are integers, every value $f'(e)$ is an integer. Therefore induction shows that every flow produced by Ford-Fulkerson is integer-valued. [guided] We prove the integrality assertion by induction over the sequence of augmentations. The starting point is the zero flow $f_0:E \to \mathbb{Z}_{\geq 0}$ defined by $f_0(e)=0$ for every $e\in E$, so the base case holds. Now suppose the current flow $f:E \to \mathbb{Z}_{\geq 0}$ is integer-valued. The residual network has labelled residual arcs, not merely ordered pairs of vertices. For each original edge $e\in E$, the forward residual arc $a_{e,+}$ has residual capacity \begin{align*} r_f(a_{e,+})=c(e)-f(e), \end{align*} and the backward residual arc $a_{e,-}$ has residual capacity \begin{align*} r_f(a_{e,-})=f(e). \end{align*} Both quantities are integers because both $c(e)$ and $f(e)$ are integers. The labels matter when the network has antiparallel original edges: the backward residual arc of $e=(u,v)$ is distinct from the forward residual arc of a different edge $(v,u)$. An augmenting path $P$ uses only residual arcs of positive residual capacity. Its bottleneck capacity is \begin{align*} \delta(P)=\min_{a\in P} r_f(a). \end{align*} Because $P$ is a finite path and each $r_f(a)$ is a positive integer, the minimum is a positive integer: \begin{align*} \delta(P)\in \mathbb{Z}_{>0}. \end{align*} For each original edge $e\in E$, the augmentation defines $f':E\to\mathbb{R}_{\geq 0}$ by adding $\delta(P)$ if $a_{e,+}$ lies on $P$, subtracting $\delta(P)$ if $a_{e,-}$ lies on $P$, and leaving $f(e)$ unchanged if neither labelled residual arc lies on $P$. This rule is unambiguous after removing directed cycles from $P$, because a simple directed augmenting path cannot contain both labelled residual arcs associated to the same original edge. The capacity constraints are preserved: in the forward case, $\delta(P)\leq r_f(a_{e,+})=c(e)-f(e)$ gives $f'(e)\leq c(e)$, while in the backward case, $\delta(P)\leq r_f(a_{e,-})=f(e)$ gives $f'(e)\geq 0$. The other inequality in each case follows from $f(e)\geq0$ and $f(e)\leq c(e)$. The conservation law is also preserved. At any internal vertex of the directed path $P$, exactly one residual arc of $P$ enters and exactly one residual arc of $P$ leaves. Interpreting a backward residual arc as decreasing the corresponding original flow, the entering and leaving changes contribute the same net amount $\delta(P)$ to the balance of inflow and outflow. Vertices not on $P$ have no incident changed edge, and the endpoints $s$ and $t$ are allowed to change because they determine the value of the flow. Hence $f'$ is a feasible $s$-$t$ flow. Finally, each value $f'(e)$ is obtained from integers by adding, subtracting, or doing nothing with the integer $\delta(P)$, so $f'$ is integer-valued. This completes the induction. [/guided] [/step] [step:Bound the number of augmentations by the capacity leaving the source] Define the source-out capacity $C_s\in\mathbb{Z}_{\geq 0}$ by \begin{align*} C_s := \sum_{\{w\in V:(s,w)\in E\}} c(s,w). \end{align*} For every feasible flow $f$, the capacity constraints give \begin{align*} |f| = \sum_{\{w\in V:(s,w)\in E\}} f(s,w) - \sum_{\{u\in V:(u,s)\in E\}} f(u,s) \leq \sum_{\{w\in V:(s,w)\in E\}} f(s,w) \leq C_s. \end{align*} Each augmentation along a path $P$ increases the flow value by exactly $\delta(P)$. From the previous step, $\delta(P)\in \mathbb{Z}_{>0}$, so each augmentation increases the value by at least $1$. Since the flow value starts at $0$ and is always at most $C_s$, at most $C_s$ augmentations can occur. Therefore the Ford-Fulkerson method terminates after finitely many augmentations. [/step] [step:Use the terminal residual network to build a certifying cut] Let $f$ be the flow when the algorithm terminates. Since the algorithm has stopped, there is no augmenting path from $s$ to $t$ in the labelled residual network. Define \begin{align*} S := \{v\in V : \text{there is a directed residual path from } s \text{ to } v\} \end{align*} and set \begin{align*} T := V\setminus S. \end{align*} Then $s\in S$ and $t\in T$. If $e=(u,v)\in E$ with $u\in S$ and $v\in T$, then the labelled forward residual arc $a_{e,+}$ cannot have positive residual capacity; otherwise $v$ would also be reachable from $s$. Hence \begin{align*} c(e)-f(e)=0, \end{align*} so \begin{align*} f(e)=c(e). \end{align*} If $e=(u,v)\in E$ with $u\in T$ and $v\in S$, then the labelled backward residual arc $a_{e,-}$ cannot have positive residual capacity; otherwise $u$ would be reachable from $s$ from the reachable vertex $v$. Hence \begin{align*} f(e)=0. \end{align*} [/step] [step:Compare the terminal flow value with the certifying cut capacity] For an $s$-$t$ cut $(S,T)$, define its capacity by \begin{align*} c(S,T):=\sum_{\{(u,v)\in E:u\in S,\ v\in T\}} c(u,v). \end{align*} Summing the conservation law over all vertices in $S\setminus\{s\}$ cancels all contributions from edges with both endpoints in $S$ and gives \begin{align*} |f| = \sum_{\{(u,v)\in E:u\in S,\ v\in T\}} f(u,v) - \sum_{\{(u,v)\in E:u\in T,\ v\in S\}} f(u,v). \end{align*} By the previous step, every edge from $S$ to $T$ is saturated and every edge from $T$ to $S$ carries zero flow. Therefore \begin{align*} |f| = \sum_{\{(u,v)\in E:u\in S,\ v\in T\}} c(u,v) = c(S,T). \end{align*} Now let $g:E \to \mathbb{R}_{\geq 0}$ be any feasible $s$-$t$ flow. The same cut identity gives \begin{align*} |g| = \sum_{\{(u,v)\in E:u\in S,\ v\in T\}} g(u,v) - \sum_{\{(u,v)\in E:u\in T,\ v\in S\}} g(u,v) \leq \sum_{\{(u,v)\in E:u\in S,\ v\in T\}} g(u,v) \leq \sum_{\{(u,v)\in E:u\in S,\ v\in T\}} c(u,v) = c(S,T). \end{align*} Since $|f|=c(S,T)$, every feasible flow $g$ satisfies $|g|\leq |f|$. Thus the terminal flow $f$ is a maximum flow. The induction step already proved that $f$ is integer-valued, so the final flow is an integer-valued maximum $s$-$t$ flow. [/step]