Max Flow = Min Cut

In this lesson, we want to prove that the Ford-Fulkerson method is actually guaranteed to find a maximum flow. To do this, we’ll take a short detour into the territory of another graph problem, finding minimum cuts.

The minimum cut problem

The minimum cut problem is another problem that can be posed in a flow network $G = (V, E, c)$. Given a source $s$ and a sink $t$, an $\mathbf{s}$-$\mathbf{t}$-cut is a partition of the vertices $V$ into two subsets $S$ and $T$, such that $s \in S$ and $t \in T$.

The value $v(S, T)$ of an $s$-$t$-cut is the capacity of all edges that cross the cut from $S$ to $T$.

$$v(S, T) = \sum_{u \in S, v \in T, (u, v) \in E} c(u, v).$$

As an example, let’s take another look at the flow network from the previous lesson:

Here, we’ve marked up an example cut with $S = \{s, a\}$ (blue) and $T = \{b, t\}$ (red). The edges crossing through the border of the cut are marked in green. The value of the cut is

$$v(S, T) = 1 + 2 + 5 = 8.$$

However, it is not a minimum cut because there is a cut with a smaller value:

This cut ...