= Solution
\b[No: the increase need not equal $\varepsilon$.] For a simple counterexample, use two edge-disjoint paths $s\to a\to t$ and $s\to b\to t$, with all four capacities equal to one. Initially the <maximum flow> is $2$. After every capacity increases to $1+\varepsilon$, send $1+\varepsilon$ down each path; a source <cut of a flow network> bounds the total by the same value. Hence
$$
\boxed{\text{new maximum}=2+2\varepsilon,\qquad\text{increase}=2\varepsilon}.
$$
More generally, by the <max-flow min-cut theorem>, if $m(S)$ is the number of directed edges leaving a <cut of a flow network>, <uniform capacity perturbation of a flow network> gives
$$
\boxed{v(\varepsilon)=\min_{S:s\in S,\,t\notin S}\bigl(c(S)+\varepsilon m(S)\bigr)}.
$$
The number of outgoing edges, and possible changes of the minimising <cut of a flow network>, determine the increase. If the question were interpreted as asking for an increase of at least $\varepsilon$, this does hold when the graph has a directed $s$-to-$t$ path, because then every <cut of a flow network> has $m(S)\geq1$. Without such a path a zero-edge <cut of a flow network> remains of capacity zero and the maximum can stay zero. Thus neither an exact increment nor an unconditional positive increment follows merely by adding the same amount to every edge capacity.
Back to article page
