Past exam of the mathematics course of the University of Cambridge / 2017 / ib / Paper 4 / 20H / d

No: the increase need not equal $\epsilon$. 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+\epsilon$, send $1+\epsilon$ down each path; a source cut of a flow network bounds the total by the same value. HenceMore 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 givesThe 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 $\epsilon$, this does hold when the graph has a directed $s$-to-$t$ path, because then every cut of a flow network has $m(S)\ge 1$. 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.