Maxflow-Mincut Theorem

The maximum flow of a network is equal to the size of the minimum cut.

Proof:

We have the easy $\le$ direction from Lemma (Maxflow is at Most the Mincut). So, in the reverse direction, consider the maximum flow $F$, where it is impossible for us to create an augmenting path to apply lemma to increase it.

On the other hand, we can create a partial augmenting path. We start at the source, but we don’t need to end at the sink. It’s edges are in $G\setminus F$ or reverse edges in $F$. Let

$$\begin{array}{rl}S& =\{\text{endpoints of a partial augmenting path}\}\\ T& =V\setminus S\end{array}$$

Since there’s no partial augmenting path that ends at the sink, then the sink must be in $T$. This allows us to define a cut $C=(S,T)$ with this partition.

I claim that $\text{size}(C)=\text{size}(F)$. First, there is no edge from $S\to T$. Suppose by contradiction there was. But then this means there is a partial augmenting path with an endpoint in $T$, contradicting the definition of $S$. This implies the flow is equal to the capacity.

Likewise, we cannot have an edge from $T\to S$. Otherwise, the reverse of it would be $S\to T$, giving us a contradiction.

This allows us to compute $\text{size}(F)$:

$$\begin{array}{rl}\text{size}(F)& =|\{\text{edges from S→T}\}|-|\{\text{edges from T→S}\}|\\ & =|\{\text{edges in G from S→T}\}|-0\\ & =\text{size}(C)\end{array}$$

where the last equality is by definition. But this tell us,

$$\begin{array}{rl}& (\forall F,C)(\text{size}(F)\le \text{size}(C))\\ & (\exists F_0,C_0)(\text{size}(F_0)=\text{size}(C_0))\end{array}$$

Indeed, for all flows $F$,

$$\text{size}(F)\le \text{size}(C_0)=\text{size}(F_0)⟹\text{maxflow}=F_0$$

and for all cuts $C$,

$$\text{size}(C)\ge \text{size}(F_0)=\text{size}(C_0)⟹\text{mincut}=C_0$$

Therefore the maxflow and mincut are equal.

Applications

We can apply this to Konig’s Theorem by turning it into a network graph where the directed edges are from $L\to R$, and that we can create an arbitrary source vertex connecting all of $L$, (i.e. $N(\text{source})=L$) and an arbitrary sink vertex where $N(\text{sink})=R$. This gives a correspondence from matchings in $G$, to flows in $N$.

We can also apply this to Menger’s Theorem. Replace each edge with two directed edges in the opposite direction to form a network. If we can remove edges to separate $S,T$, then it defines a cut $C$. Then $\text{size}(C)$ is at most the number of removed edges. But for a minimum cut, this is equal to the maxflow. Indeed, there exists a flow $F$ where $\text{size}(F)=\text{size}(C)=k$.

If $F$ is a flow of size at least $k$, then it contains $k$ edge disjoint $S\to T$ paths. We can prove this by induction on $k$. For $k=1$, we start at $S$ and create a path by adding new edges to $F$ until we get stuck (in particular, $T$). Suppose we stopped at some vertex $v$. For each ingoing edge to $v$, we take an outgoing edge, except for the last one such that we cannot get stuck. At $S$, the number of outgoing is ingoing plus $k$. So, we cannot get stuck here. Thus we can only stop at $T$.

For the inductive step, consider a $S\to T$ path $P$. We induct on $F-P$, giving us $k-1$ edge disjoint paths. The proof is trivial from here.