Home › Mathematics › Graph Theory › Max-Flow Min-Cut Theorem
Graph Theory Operations Research 📅 Updated: Nov 12, 2025 ⏱️ 12 min read

Max-Flow Min-Cut Theorem

A foundational result in network flow theory stating that the maximum amount of flow passing from a source to a sink is equal to the capacity of the minimum cut separating them.

The Max-Flow Min-Cut Theorem is a cornerstone of combinatorial optimization and network flow theory. First proved by Lester R. Ford Jr. and Delbert Ray Fulkerson in 1956, the theorem establishes a fundamental duality between two seemingly distinct problems in a flow network: maximizing the flow from a source to a sink, and finding the minimum capacity cut that separates them.

This result not only provides deep theoretical insight into the structure of networks but also serves as the mathematical foundation for numerous algorithms used in computer science, operations research, telecommunications, and logistics.

Formal Statement & Definitions

To state the theorem precisely, we first define a flow network:

Flow Network

A directed graph G = (V, E) where each edge (u, v) ∈ E has a non-negative capacity c(u, v) ≥ 0. Two special vertices are designated: a source s ∈ V and a sink t ∈ V.

A flow f is a function f: E → ℝ satisfying:

  • Capacity constraint: 0 ≤ f(u, v) ≤ c(u, v) for all edges.
  • Flow conservation: For every vertex v ≠ s, t, ∑ f(u, v) = ∑ f(v, w).

The value of the flow is |f| = ∑ f(s, v) - ∑ f(v, s).

Cut

An (s, t)-cut is a partition of vertices V into two sets S and T such that s ∈ S and t ∈ T. The capacity of the cut is C(S, T) = ∑_{u∈S, v∈T} c(u, v).

Theorem (Max-Flow Min-Cut):
In any flow network G, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut.

max |f| = min C(S, T)

Historical Context

The theorem emerged from Ford and Fulkerson's 1956 paper on the Soviet railway problem, where they sought to determine the maximum freight capacity between Moscow and Leningrad. Their work built upon earlier contributions by Tiberius Cvitanović (1931) on planar graphs and Jack Edmonds's later refinements.

The result revolutionized operations research by providing a constructive method (the Ford-Fulkerson algorithm) to solve maximum flow problems efficiently. It also inspired the development of linear programming duality theory and modern combinatorial optimization.

Algorithms & Computation

The theorem's constructive proof naturally yields the Ford-Fulkerson method, which iteratively finds augmenting paths in the residual graph and increases flow until no such paths remain. The maximum flow reached equals the minimum cut capacity.

Key variants include:

  • Edmonds-Karp Algorithm: Uses BFS to find shortest augmenting paths. Time complexity: O(VE²).
  • Dinic's Algorithm: Employs level graphs and blocking flows. Time complexity: O(V²E), or O(E√V) for unit capacities.
  • Push-Relabel Algorithms: Local preflow methods that often outperform path-augmentation approaches in practice.
3 4 2 1 2 s A B t

Figure 1: Sample flow network with capacities. Maximum flow = 4, Minimum cut = {(s,A), (s,B)} with capacity 3+1=4.

Real-World Applications

The theorem's versatility extends far beyond theoretical computer science:

  • Transportation Networks: Optimizing freight, traffic, or pipeline capacity between origin and destination.
  • Telecommunications: Maximizing data throughput in network routing and bandwidth allocation.
  • Image Segmentation: Used in computer vision (GraphCut algorithm) to separate foreground from background.
  • Project Scheduling: Determining critical bottlenecks in resource-constrained workflows.
  • Bipartite Matching: Reducing maximum matching problems to max-flow for efficient solutions.

Simplified Proof Sketch

The proof relies on two inequalities:

  1. Weak Duality: For any feasible flow f and any cut (S, T), |f| ≤ C(S, T). This follows from flow conservation and capacity constraints.
  2. Constructive Equality: When the Ford-Fulkerson algorithm terminates, the set S of vertices reachable from s in the residual graph defines a cut where every edge from S to T is saturated. Thus, |f| = C(S, T), proving optimality.

Together, these establish that the maximum flow value cannot exceed the minimum cut capacity, and an algorithm exists that achieves equality.

References

  1. [1] Ford, L. R., & Fulkerson, D. R. (1956). "Maximal Flow Through a Network". Canadian Journal of Mathematics, 8, 399–404.
  2. [2] Kleinberg, J., & Tardos, É. (2006). Algorithm Design. Pearson. Chapter 7: Maximum Network Flow.
  3. [3] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
  4. [4] Borůvka, O. (1928). "O jistém problému minimálním". Práce Moravské přírodovědecké společnosti, 3, 37–58.
}