Algorithm description. Start with $f(e) = 0$ for all $e$. Repeat: find an $s$-$t$ path $P$ in the residual graph $G_f$; augment $f$ along $P$ by the bottleneck capacity $\delta = \min_{e \in P} c_f(e)$. Stop when no $s$-$t$ path exists in $G_f$.

Invariant: $f$ is a valid flow after each augmentation. Initially $f \equiv 0$ is valid. Augmenting along $P$: for forward edges $(u,v) \in P$, increase $f(u,v)$ by $\delta$; for backward edges, decrease $f(v,u)$ by $\delta$. The capacity constraint holds because $\delta \leq c_f(e)$ ensures $f(e) \leq c(e)$ and $f(e) \geq 0$. Flow conservation holds because augmentation changes inflow and outflow at each internal vertex by equal amounts ($\delta$ in and $\delta$ out along the path).

Monotonicity. Each augmentation increases $|f|$ by $\delta > 0$. For integer capacities, $\delta \geq 1$, so $|f|$ increases by at least 1 per iteration. Since $|f| \leq |f^*| < \infty$, termination occurs in at most $|f^*|$ iterations.

Optimality at termination. When the algorithm terminates, no $s$-$t$ path exists in $G_f$. As shown in the max-flow min-cut proof: define $S = \{v : v \text{ reachable from } s \text{ in } G_f\}$. Then $|f| = c(S, V\setminus S) = \text{some cut capacity}$. By weak duality, $|f| \leq$ max flow $\leq$ min cut $\leq c(S, V\setminus S) = |f|$. So $|f|$ is the max flow.

Edmonds-Karp bound. When augmenting paths are chosen by BFS (shortest paths in $G_f$): the distance $d(s, v)$ in $G_f$ is non-decreasing after each augmentation (key lemma, proved by considering how the residual graph changes). Each augmenting path saturates at least one edge (the bottleneck), and a saturated edge $(u,v)$ can only reappear after $d(s,u)$ increases by at least 2. Since distances are at most $n$, each edge is saturated at most $n/2$ times, giving at most $nm/2$ augmentations total. Each BFS takes $O(m)$, so total time is $O(nm^2)$.

Improved bound: More careful analysis shows $O(nm)$ augmentations suffice for Edmonds-Karp. $\square$