Course contentsShow
← Mathematics
Lesson 2705 of 3,12153. Graph TheoryFree lesson

The Max-Flow Min-Cut Theorem

State the max-flow min-cut theorem: the maximum flow value equals the capacity of a minimum cut separating source and sink.

The Max-Flow Min-Cut Theorem

What You'll Learn

You'll discover one of the most elegant and powerful results in graph theory: that the maximum amount of flow you can push through a network equals the capacity of the smallest "bottleneck" that blocks it.

The Core Idea

Imagine water flowing through a pipe network from a source (where water enters) to a sink (where it exits). Each pipe has a maximum capacity. The max-flow is the total amount you can push through the entire network per unit time.

Now imagine cutting certain pipes to completely disconnect the source from the sink—this is called a cut. The capacity of a cut is the sum of capacities of all pipes you severed that were going from the source's side toward the sink's side.

Intuitively, you'd expect the maximum flow to be limited by the weakest cut—the one with minimum capacity. The Max-Flow Min-Cut Theorem confirms this intuition perfectly:

The maximum flow value from source to sink equals the minimum cut capacity separating them.

Why This Matters

This theorem tells us two things are actually the same quantity viewed differently:

  • Max-flow: An optimization problem (maximize flow)
  • Min-cut: A different optimization problem (minimize cut capacity)

Think of it like this: the flow is "trying" to be as large as possible, while the minimum cut reveals the "true bottleneck" limiting that flow. No matter how cleverly you route the flow, you cannot exceed what the narrowest bottleneck allows.

This duality is incredibly useful—algorithms that find maximum flows (like the Ford-Fulkerson method you learned about with networks) automatically identify minimum cuts, and vice versa.

Key Takeaway: The Max-Flow Min-Cut Theorem states that in any flow network, the maximum flow value from source to sink equals the capacity of a minimum cut separating them—revealing that the bottleneck capacity exactly determines the achievable flow.