Course contentsShow
← Computer Science
Lesson 1050 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Min-Cut and Max-Flow Duality

Understand the max-flow min-cut theorem and how min-cut identifies bottleneck edges.

Min-Cut and Max-Flow Duality

What You'll Learn

You'll discover the fundamental relationship between finding the maximum flow and finding the minimum cut in a network—and why they're always equal.

The Core Idea

Imagine a network of pipes carrying water from a source to a sink. The max-flow min-cut theorem states two remarkable facts are always identical:

  1. Maximum Flow: The most water you can push from source to sink
  2. Minimum Cut: The smallest total capacity of edges you'd need to remove to completely disconnect the source from the sink

This isn't coincidence—it's a deep duality. The maximum flow is limited by the minimum cut. Think of it like this: if you remove the bottleneck edges (the min-cut), no flow can get through at all. Conversely, you can always achieve a flow equal to that cut's capacity.

Why This Matters

A cut partitions the network into two sets: nodes reachable from the source (S) and nodes on the sink's side (T). The cut's capacity is the sum of all edge capacities going from S to T.

The min-cut identifies the exact bottleneck in your network—the weakest link limiting flow. For example:

  • In transportation: which roads, if closed, would halt traffic most efficiently
  • In network security: which connections are critical vulnerabilities
  • In project scheduling: which tasks are the critical constraints

Once you've computed max-flow (using Ford-Fulkerson, Edmonds-Karp, or Dinic's), you automatically know the min-cut value—it equals the max-flow! The actual bottleneck edges are those saturated edges crossing from nodes reachable in the residual network to those that aren't.

Key Takeaway: The max-flow min-cut theorem proves that the maximum flow value always equals the minimum cut capacity, revealing the network's fundamental bottleneck and enabling powerful optimization applications.