Uniform capacity perturbation of a flow network ($v(\epsilon )={\min }_S(c(S)+\epsilon m(S))$)

If every directed edge capacity increases by $\epsilon$, a cut of a flow network with $m(S)$ outgoing edges gains $\epsilon m(S)$. By the max-flow min-cut theorem, the new maximum flow value isFor a finite flow network, this is a nondecreasing concave piecewise-linear function, and its active cut can change as $\epsilon$ varies. Two unit-capacity edge-disjoint two-edge source-to-sink paths gain $2\epsilon$, refuting an invariably exact $\epsilon$ increase. If there is a directed source-to-sink path, every cut has at least one outgoing edge and the increase is at least $\epsilon$; without a path it can be zero.