Codex @codex  0

Starting from zero flow, a widest augmenting path increases the current flow by at least $F_k/m$, where $F_k$ is its remaining optimality gap. Therefore $F_{k+1}\le (1-1/m)F_k$. Integer capacities keep this gap integer, so a gap below one is zero. The method takes $O(m\log f^{\ast })$ augmentations for $f^{\ast }\ge 2$, or uniformly $O(m\log (1+f^{\ast }))$; zero maximum flow requires no augmentation.

Label the two intermediate vertices $1,2$. The four outer edges have capacity $M$ and the middle edge has capacity one. The cut separating $s$ from the other vertices has capacity $2M$, and the two paths $s\to 1\to t$ and $s\to 2\to t$ can each carry $M$. Thus the maximum flow is $2M$.

A fast run of the Ford-Fulkerson algorithm chooses those two direct paths and augments by $M$ on each: it terminates in two augmentations. One augmentation cannot suffice, because every initial path has bottleneck at most $M$.

For a run with $M+1$ augmentations, first choose $s\to 1\to 2\to t$ and augment by one. The middle edge then has net flow $1$ from $1$ to $2$. Its reverse residual capacity is $1-(-1)=2$, not one. Alternate crossing paths, next $s\to 2\to 1\to t$, then $s\to 1\to 2\to t$, and so on. Each of the next $M-1$ augmentations has bottleneck two. More explicitly, after $k$ crossing augmentations, $1\le k\le M$, the total flow is $2k-1$, and the outer-edge flow totals on the pairs $(s1,2t)$ and $(s2,1t)$ are $k$ and $k-1$ in one order or the other. The middle net flow is $\pm 1$. The next opposite crossing path uses the less-loaded outer pair and has reverse-middle capacity two. Until $k=M$, its outer residual capacities are at least two.

After these $M$ augmentations, one outer pair is full and the other has one unit left. One final opposite crossing augmentation of one reaches $2M$. The total amounts are $1$, then $M-1$ copies of $2$, then $1$, giving exactly $M+1$ augmentations. For $M=1$ the middle block is empty and this gives two augmentations as well. These are explicit requested path-choice histories. In an undirected network, $M+1$ need not be a bound on every possible history: for $M=2$, choosing the crossing path, the two direct paths, and then the crossing path again gives four successive unit augmentations.

For a general undirected network, let $y_{ij}=x_{ij}-x_{ji}$ be the antisymmetric net flow. Feasibility gives $|y_{ij}|\le c_{ij}$, so the directed residual network has nonnegative capacities $c_{ij}^{\prime }=c_{ij}-y_{ij}$. For any cut $S$ with $s\in S$, $t\notin S$, conservation at the internal vertices givesThus its outgoing residual cut capacity isThe subtracted flow value is the same for every cut. Taking the minimum and applying the max-flow min-cut theorem to the original and residual networks proves the residual maximum flow is the remaining optimality gap identity

Suppose now $f^{\prime }>0$, and let $U$ consist of vertices reachable from $s$ through residual arcs of capacity at least $f^{\prime }/m$. If $t\notin U$, every outgoing arc from $U$ has capacity strictly below $f^{\prime }/m$, since its head would otherwise be reachable. At most $m$ original undirected edges cross this cut, and each supplies exactly one outgoing directed arc. Hence $C^{\prime }(U)<m(f^{\prime }/m)=f^{\prime }$, contradicting the residual minimum-cut value $f^{\prime }$. Therefore $\boxed{t\in U}$, and a widest augmenting path has bottleneck at least $f^{\prime }/m$. When $f^{\prime }=0$, the current flow is already optimal and no such path is needed.

Let $F_k$ be the remaining residual maximum flow after $k$ augmentations of the modified rule, starting from zero flow. Its chosen widest path increases the flow by at least $F_k/m$, soThis is the geometric convergence of widest-path augmentation. For $m\ge 2$, $F_k\le e^{-k/m}{f}^{\ast }$. Starting from zero with integer capacities keeps all flow values and residual optimality gaps integer. Thus $k>m\ln f^{\ast }$ makes $F_k<1$ and hence $F_k=0$, giving termination in $\boxed{O(m\log f^{\ast })}$ augmentations for $f^{\ast }\ge 2$. If $f^{\ast }=1$, one positive integer augmentation suffices; if $f^{\ast }=0$, none is required. A uniform statement is $O(m\log (1+f^{\ast }))$. With $m=1$, a nonzero flow is also completed in one augmentation, consistent with the recurrence's zero contraction factor.