Max Flow Minimum Cut - after removing an edge

Question

Suppose that the max flow of a network is $|f|$ and there's a minimum-cut $(S,T)$ such that $e$ is an edge which crosses the cut.

Why is it must be that the max flow after removing $e$ is exactly $|f|-c(e)$?

Answer 1

Let's try to answer it the opposite way: what would happen if the max flow after removing $e$ was different than $|f|-c(e)$ ? It can't be greater than that, because $(S,T)$ is still a valid cut. Contradiction.

So it has to be strictly less than $|f|-c(e)$. By the max-flow/min-cut theorem, there is a cut $(U',V')$ with value $k<|f|-c(e)$. If $e$ goes from $U'$ to $V'$, that means $(U',V')$ was a cut with value smaller than $|f|$ in the first graph. If $e$ is contained in $U'$ or $V'$, then $(U',V')$ was a cut with value $k<|f|-c(e)<|f|$ in the first graph. Contradiction again.

Hence, the max flow of the graph without $e$ is $|f|-c(e)$.

Answer 2

This follows directly from the Max-Flow Min-Cut theorem.

Since $e$ is part of the minimum cut, after removing it, we have necessarily decreased the maximum possible flow (by the Max-flow Min-Cut Theorem) by the capacity of $e$, i.e. the maximum flow must now be $|f|-e$, as you stated.

The outline of the proof of the Max-Flow Min-Cut theorem is as follows: we use the Ford-Fulkerson algorithm to find a maximum flow.

The Ford-Fulkerson algorithm defines a residual graph $G_f$ for the final flow assignment. We now make a cut as follows (divide the graph into two parts): $A$ is the part of $G$ which is reachable from $G_f$, and $A^c$ is the rest of the graph.

Since any flow in the network is less than or equal to the capacity of every cut in the network (this is the key point/idea), the given cut must be the minimum cut which achieves the maximum flow if we can show that the capacity of the given cut $(A,A^c)$ is equal to the maximum flow computed by Ford-Fulkerson.

This follows if we can show the two following facts:

1. All outgoing edges from the cut are fully saturated.
2. All incoming edges to the cut must have zero flow.

For details see here: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

or better yet, Papadimitriou and Steiglitz's Combinatorial Optimization.