Max Flow = Min Cut

Explore the connection between maximum flows and minimum cuts.

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)G = (V, E, c). Given a source ss and a sink tt, an s\mathbf{s}-t\mathbf{t}-cut is a partition of the vertices VV into two subsets SS and TT, such that sSs \in S and tTt \in T.

The value v(S,T)v(S, T) of an ss-tt-cut is the capacity of all edges that cross the cut from SS to TT.

v(S,T)=uS,vT,(u,v)Ec(u,v).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:

Get hands-on with 1200+ tech skills courses.