Increase edge capacity under some consideration won't change max-flow

Question

I want to prove that if we have a graph G and and maximum flow in it F,then if we change each edge capacity under below considerations the max flow won't change:

$\forall e \in E, \qquad c^\prime(e) \geq c(e)$

$\forall e \in E,\qquad f(e) = c(e) \Rightarrow c^\prime(e) = c(e)$

I can understand it intuitively but i cannot find a mathematical proof for it,any ideas?

Answer 1

Intuitively: Let $C$ be any minimum cut and let $f$ be a maximum flow. Then each edge in $C$ is at capacity. If you increase the capacity of any subset of any edge not in $C$, each edge by any nonnegative amount, then $C$ will still remain a cut with the same capacity, and furthermore, the capacity of any other cut, if it changes, will only increase. So the capacity of the minimum cut will not change. Furthermore, $f$ is still a feasible flow (make sure you see why), and as the capacity of the minimum cut hasb't changed, it follows that $f$ is still a maximum flow.

Answer 2

Suppose that we have a maximal flow $F$ in $G$. Then there is no augmenting path in the network, for if there were, by the Ford-Fulkerson algorithm, $F$ would not be maximal.

Now suppose the capacities are changed as described to give a new network $G'$. Since no capacity decreases, $F$ is still a valid flow in $G'$. Also, $F$ is maximal in $G'$ since the changes described do not create any augmenting paths. Recall that a path is augmenting if and only if the smallest residual along the path is greater than zero.

More explicitly, consider an $S-T$ path $P$ in $G$. Since this is not an augmenting path, there is some edge $e$ in $P$ with $c(e)=f(e)$. Otherwise the residual in every edge in $P$ would be positive, and we could increase $F$ by $\min(\{c(e)-f(e)|e\in P\})$. For any such $e$, $c'(e)=c(e)=f(e)$ so $P$ is not an augmenting path in $G'$.