Maximum Flow and Minimum Cut: The Theorem That Ties Them Together
- Max flow min cut theorem: the maximum flow from source to sink always equals the minimum cut capacity — same number, two ways to read the same terminal residual graph
- Residual graph: backward edges are the undo mechanism that lets Ford-Fulkerson correct greedy routing mistakes without restarting
- Edmonds-Karp uses BFS instead of DFS to guarantee shortest augmenting paths, capping steps at O(VE) for O(VE²) total — avoiding the O(E · max_flow) trap
- Applications: bipartite matching via König's theorem, network reliability, and image segmentation all reduce directly to the min cut
- Interview disguises: independent paths, vertex removal, project selection, and assignment problems are all max flow problems in costume
- Two critical bugs: forgetting to initialize reverse edges to capacity 0, and accidentally using a stack instead of a queue for BFS
You have a network. Water flows through pipes. Or packets route through servers. Or passengers shuffle through airport connections while the gate agent pretends not to see them. One question sits at the center of all of them: how much total flow can actually make it from source to sink?
That is the maximum flow problem. And buried inside its solution is a free answer to a completely different question. The minimum cut, the smallest set of edges you'd need to sever to disconnect source from sink, always has exactly the same value as the max flow. Not approximately. Not usually. Always. This is the max-flow min-cut theorem, and it's the kind of result that makes you stare at the ceiling for a minute.
A Flow Network Is a Graph With Rules
A flow network is a directed graph where every edge has a capacity, a non-negative integer representing the maximum rate it can carry. Two nodes get special treatment: a source (where flow originates) and a sink (where flow exits).
Think water pipes. Pipes have diameters. Water enters at the reservoir, exits at consumers. You want the maximum delivery rate. Pretty physical, pretty grounded.
A valid flow must obey two constraints:
- Capacity constraint: flow on each edge cannot exceed its capacity
- Conservation constraint: for every node except source and sink, total flow in equals total flow out
The value of a flow is the total leaving the source. By conservation, that always equals the total entering the sink. No flow vanishes in the middle. You are not running a hedge fund.
A Concrete Example
Five nodes: S (source), A, B, T (sink). Edges:
| Edge | Capacity |
|---|---|
| S → A | 3 |
| S → B | 2 |
| A → T | 2 |
| A → B | 1 |
| B → T | 3 |
What is the maximum flow from S to T?
One solution: send 2 units along S→A→T, then 1 unit along S→A→B→T, then 2 units along S→B→T. Total at T: 2 + 1 + 2 = 5.
Can you do better? The source S has total outgoing capacity 3 + 2 = 5. That is a hard ceiling. So 5 is optimal and we already found it. Sometimes the answer is right there.
The Algorithm That Fixes Its Own Mistakes
The foundational idea: find a path from source to sink with remaining capacity, push as much flow as possible through it, repeat until no such path exists.
The tricky part is undoing bad decisions. If you greedily route flow one way early on, you might block a better routing you discover later. Every programmer has experienced this with architecture decisions. The residual graph is the mechanism that lets you course-correct.
For every edge (u, v) with capacity c carrying current flow f:
- Add a forward edge (u, v) with residual capacity c - f
- Add a backward edge (v, u) with residual capacity f
The backward edge is the undo button. If a future augmenting path routes flow backward along (v, u), it cancels some of the flow you previously sent forward, effectively rerouting it. The algorithm gets to take back its mistakes. We should all be so lucky.
Ford-Fulkerson in pseudocode:
while there exists a path P from source to sink in residual graph:
bottleneck = min(residual capacity of each edge in P)
for each edge (u, v) in P:
graph[u][v] -= bottleneck
graph[v][u] += bottleneck
return total flow out of source
Here is the problem with basic Ford-Fulkerson: if you use DFS to find paths and capacities are large integers, the algorithm can take O(max_flow) iterations. For a graph where the max flow is 10^9, that is a billion iterations. You will grow old waiting.
Edmonds-Karp fixes this by using BFS. BFS always finds the shortest augmenting path (fewest edges). With that choice, the number of augmentation steps is bounded at O(VE), giving a total complexity of O(VE²). The BFS per step is O(V + E), and Edmonds-Karp runs at most O(VE) steps. Small polynomial, not civilization-ending exponential.
Cut the Network in Half
A cut (S-side, T-side) is a partition of all nodes: one set contains the source, one contains the sink. The capacity of a cut is the sum of capacities on edges going from the S-side to the T-side. Edges flowing the other direction do not count.
Back to the example. Two possible cuts:
Cut 1 ({S} vs {A, B, T}): edges crossing are S→A (3) and S→B (2). Cut capacity = 5.
Cut 2 ({S, A} vs {B, T}): edges crossing are S→B (2), A→T (2), A→B (1). Cut capacity = 5.
The minimum cut is the partition with the smallest capacity. Why does this matter? Every unit of flow must cross every cut. So no flow can exceed the capacity of any cut. The minimum cut is an upper bound on the max flow.
The Theorem That Makes You Stare at the Ceiling
The theorem: the maximum flow from source to sink equals the capacity of the minimum cut.
The upper bound direction is obvious. Max flow cannot exceed any cut's capacity. The surprise is that the max flow actually reaches the minimum cut with no gap at all.
Proof sketch: when Ford-Fulkerson terminates, no path from source to sink exists in the residual graph. Let S* be the nodes reachable from the source in that final residual graph. The sink is not in S*. Every forward edge from S* to V \ S* must be fully saturated, otherwise its endpoint would be reachable. Every backward edge from V \ S* to S* carries zero flow, otherwise its reverse residual edge would be available.
So the flow across this cut equals the sum of forward edge capacities exactly. That is simultaneously the max flow and the min cut. Same number. Two completely different questions. One answer.
Tracing the Algorithm on Our Example
Starting graph (residual = capacity, no flow yet):
S→A: 3, S→B: 2, A→T: 2, A→B: 1, B→T: 3
Step 1: BFS finds S→A→T (length 2). Bottleneck = min(3, 2) = 2.
S→A: 1, A→S: 2, A→T: 0, T→A: 2
(S→B, A→B, B→T unchanged)
Step 2: BFS finds S→A→B→T (length 3). Bottleneck = min(1, 1, 3) = 1.
S→A: 0, A→S: 3, A→B: 0, B→A: 1, B→T: 2, T→B: 1
Step 3: BFS finds S→B→T (length 2). Bottleneck = min(2, 2) = 2.
S→B: 0, B→S: 2, B→T: 0, T→B: 3
Step 4: BFS finds no path from S to T. Done.
Total flow = 2 + 1 + 2 = 5.
To find the min cut: check which nodes are reachable from S in the final residual graph. S→A has 0 residual, S→B has 0 residual. Only S is reachable. Cut = {S} vs {A, B, T}, capacity = 3 + 2 = 5. Confirmed.
One Structure, Every Language
Edmonds-Karp uses an adjacency matrix for the residual graph. Time: O(VE²). Space: O(V²) for the matrix plus O(V) for BFS state.
# Python 3 from collections import deque def max_flow(graph: list[list[int]], source: int, sink: int, n: int) -> int: def bfs(parent: list[int]) -> bool: visited = {source} queue = deque([source]) while queue: u = queue.popleft() for v in range(n): if v not in visited and graph[u][v] > 0: visited.add(v) parent[v] = u if v == sink: return True queue.append(v) return False flow = 0 while True: parent = [-1] * n if not bfs(parent): break path_flow = float('inf') v = sink while v != source: u = parent[v] path_flow = min(path_flow, graph[u][v]) v = u flow += path_flow v = sink while v != source: u = parent[v] graph[u][v] -= path_flow graph[v][u] += path_flow v = u return flow
# Python 2 from collections import deque def max_flow(graph, source, sink, n): def bfs(parent): visited = {source} queue = deque([source]) while queue: u = queue.popleft() for v in xrange(n): if v not in visited and graph[u][v] > 0: visited.add(v) parent[v] = u if v == sink: return True queue.append(v) return False flow = 0 while True: parent = [-1] * n if not bfs(parent): break path_flow = float('inf') v = sink while v != source: u = parent[v] path_flow = min(path_flow, graph[u][v]) v = u flow += path_flow v = sink while v != source: u = parent[v] graph[u][v] -= path_flow graph[v][u] += path_flow v = u return flow
// JavaScript function maxFlow(graph, source, sink, n) { function bfs(parent) { const visited = new Set([source]); const queue = [source]; let i = 0; while (i < queue.length) { const u = queue[i++]; for (let v = 0; v < n; v++) { if (!visited.has(v) && graph[u][v] > 0) { visited.add(v); parent[v] = u; if (v === sink) return true; queue.push(v); } } } return false; } let flow = 0; while (true) { const parent = new Array(n).fill(-1); if (!bfs(parent)) break; let pathFlow = Infinity; for (let v = sink; v !== source; v = parent[v]) pathFlow = Math.min(pathFlow, graph[parent[v]][v]); flow += pathFlow; for (let v = sink; v !== source; v = parent[v]) { const u = parent[v]; graph[u][v] -= pathFlow; graph[v][u] += pathFlow; } } return flow; }
// TypeScript function maxFlow(graph: number[][], source: number, sink: number, n: number): number { function bfs(parent: number[]): boolean { const visited = new Set<number>([source]); const queue: number[] = [source]; let i = 0; while (i < queue.length) { const u = queue[i++]; for (let v = 0; v < n; v++) { if (!visited.has(v) && graph[u][v] > 0) { visited.add(v); parent[v] = u; if (v === sink) return true; queue.push(v); } } } return false; } let flow = 0; while (true) { const parent: number[] = new Array(n).fill(-1); if (!bfs(parent)) break; let pathFlow = Infinity; for (let v = sink; v !== source; v = parent[v]) pathFlow = Math.min(pathFlow, graph[parent[v]][v]); flow += pathFlow; for (let v = sink; v !== source; v = parent[v]) { const u = parent[v]; graph[u][v] -= pathFlow; graph[v][u] += pathFlow; } } return flow; }
// Java import java.util.*; public class MaxFlow { private static int[] parent; private static boolean bfs(int[][] graph, int source, int sink, int n) { boolean[] visited = new boolean[n]; visited[source] = true; Queue<Integer> queue = new LinkedList<>(); queue.add(source); while (!queue.isEmpty()) { int u = queue.poll(); for (int v = 0; v < n; v++) { if (!visited[v] && graph[u][v] > 0) { visited[v] = true; parent[v] = u; if (v == sink) return true; queue.add(v); } } } return false; } public static int solve(int[][] graph, int source, int sink, int n) { parent = new int[n]; int flow = 0; while (bfs(graph, source, sink, n)) { int pathFlow = Integer.MAX_VALUE; for (int v = sink; v != source; v = parent[v]) pathFlow = Math.min(pathFlow, graph[parent[v]][v]); flow += pathFlow; for (int v = sink; v != source; v = parent[v]) { int u = parent[v]; graph[u][v] -= pathFlow; graph[v][u] += pathFlow; } } return flow; } }
// C++ #include <climits> #include <queue> #include <vector> bool bfs(std::vector<std::vector<int>>& graph, int source, int sink, int n, std::vector<int>& parent) { std::vector<bool> visited(n, false); visited[source] = true; std::queue<int> q; q.push(source); while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 0; v < n; v++) { if (!visited[v] && graph[u][v] > 0) { visited[v] = true; parent[v] = u; if (v == sink) return true; q.push(v); } } } return false; } int maxFlow(std::vector<std::vector<int>>& graph, int source, int sink, int n) { std::vector<int> parent(n); int flow = 0; while (bfs(graph, source, sink, n, parent)) { int pathFlow = INT_MAX; for (int v = sink; v != source; v = parent[v]) pathFlow = std::min(pathFlow, graph[parent[v]][v]); flow += pathFlow; for (int v = sink; v != source; v = parent[v]) { int u = parent[v]; graph[u][v] -= pathFlow; graph[v][u] += pathFlow; } } return flow; }
// C #include <limits.h> #include <stdbool.h> #define MAXN 200 static int parent[MAXN]; bool bfs(int graph[MAXN][MAXN], int source, int sink, int n) { bool visited[MAXN] = {false}; int queue[MAXN], front = 0, back = 0; visited[source] = true; queue[back++] = source; while (front < back) { int u = queue[front++]; for (int v = 0; v < n; v++) { if (!visited[v] && graph[u][v] > 0) { visited[v] = true; parent[v] = u; if (v == sink) return true; queue[back++] = v; } } } return false; } int maxFlow(int graph[MAXN][MAXN], int source, int sink, int n) { int flow = 0; while (bfs(graph, source, sink, n)) { int pathFlow = INT_MAX; for (int v = sink; v != source; v = parent[v]) { int cap = graph[parent[v]][v]; if (cap < pathFlow) pathFlow = cap; } flow += pathFlow; for (int v = sink; v != source; v = parent[v]) { int u = parent[v]; graph[u][v] -= pathFlow; graph[v][u] += pathFlow; } } return flow; }
// Go import "math" func maxFlow(graph [][]int, source, sink, n int) int { parent := make([]int, n) bfs := func() bool { visited := make([]bool, n) visited[source] = true queue := []int{source} for len(queue) > 0 { u := queue[0] queue = queue[1:] for v := 0; v < n; v++ { if !visited[v] && graph[u][v] > 0 { visited[v] = true parent[v] = u if v == sink { return true } queue = append(queue, v) } } } return false } flow := 0 for bfs() { pathFlow := math.MaxInt64 for v := sink; v != source; v = parent[v] { if graph[parent[v]][v] < pathFlow { pathFlow = graph[parent[v]][v] } } flow += pathFlow for v := sink; v != source; v = parent[v] { u := parent[v] graph[u][v] -= pathFlow graph[v][u] += pathFlow } } return flow }
// Rust use std::collections::VecDeque; fn max_flow(graph: &mut Vec<Vec<i64>>, source: usize, sink: usize, n: usize) -> i64 { let mut flow = 0i64; loop { let mut parent = vec![usize::MAX; n]; let mut visited = vec![false; n]; visited[source] = true; let mut queue = VecDeque::new(); queue.push_back(source); 'outer: while let Some(u) = queue.pop_front() { for v in 0..n { if !visited[v] && graph[u][v] > 0 { visited[v] = true; parent[v] = u; if v == sink { break 'outer; } queue.push_back(v); } } } if !visited[sink] { break; } let mut path_flow = i64::MAX; let mut v = sink; while v != source { let u = parent[v]; path_flow = path_flow.min(graph[u][v]); v = u; } flow += path_flow; let mut v = sink; while v != source { let u = parent[v]; graph[u][v] -= path_flow; graph[v][u] += path_flow; v = u; } } flow }
// Swift func maxFlow(_ graph: inout [[Int]], source: Int, sink: Int, n: Int) -> Int { var flow = 0 var parent = [Int](repeating: -1, count: n) func bfs() -> Bool { parent = [Int](repeating: -1, count: n) var visited = [Bool](repeating: false, count: n) visited[source] = true var queue = [source] var i = 0 while i < queue.count { let u = queue[i]; i += 1 for v in 0..<n { if !visited[v] && graph[u][v] > 0 { visited[v] = true parent[v] = u if v == sink { return true } queue.append(v) } } } return false } while bfs() { var pathFlow = Int.max var v = sink while v != source { let u = parent[v] pathFlow = min(pathFlow, graph[u][v]) v = u } flow += pathFlow v = sink while v != source { let u = parent[v] graph[u][v] -= pathFlow graph[v][u] += pathFlow v = u } } return flow }
// Kotlin import java.util.LinkedList fun maxFlow(graph: Array<IntArray>, source: Int, sink: Int, n: Int): Int { val parent = IntArray(n) fun bfs(): Boolean { val visited = BooleanArray(n) visited[source] = true val queue = LinkedList<Int>() queue.add(source) while (queue.isNotEmpty()) { val u = queue.poll() for (v in 0 until n) { if (!visited[v] && graph[u][v] > 0) { visited[v] = true parent[v] = u if (v == sink) return true queue.add(v) } } } return false } var flow = 0 while (bfs()) { var pathFlow = Int.MAX_VALUE var v = sink while (v != source) { pathFlow = minOf(pathFlow, graph[parent[v]][v]) v = parent[v] } flow += pathFlow v = sink while (v != source) { graph[parent[v]][v] -= pathFlow graph[v][parent[v]] += pathFlow v = parent[v] } } return flow }
// C# using System.Collections.Generic; public static class MaxFlow { private static bool Bfs(int[,] graph, int source, int sink, int n, int[] parent) { var visited = new bool[n]; visited[source] = true; var queue = new Queue<int>(); queue.Enqueue(source); while (queue.Count > 0) { int u = queue.Dequeue(); for (int v = 0; v < n; v++) { if (!visited[v] && graph[u, v] > 0) { visited[v] = true; parent[v] = u; if (v == sink) return true; queue.Enqueue(v); } } } return false; } public static int Solve(int[,] graph, int source, int sink, int n) { var parent = new int[n]; int flow = 0; while (Bfs(graph, source, sink, n, parent)) { int pathFlow = int.MaxValue; for (int v = sink; v != source; v = parent[v]) pathFlow = Math.Min(pathFlow, graph[parent[v], v]); flow += pathFlow; for (int v = sink; v != source; v = parent[v]) { int u = parent[v]; graph[u, v] -= pathFlow; graph[v, u] += pathFlow; } } return flow; } }
# Ruby require 'set' def max_flow(graph, source, sink, n) bfs = lambda do |parent| visited = Set.new([source]) queue = [source] until queue.empty? u = queue.shift (0...n).each do |v| next if visited.include?(v) || graph[u][v] <= 0 visited.add(v) parent[v] = u return true if v == sink queue << v end end false end flow = 0 loop do parent = Array.new(n, -1) break unless bfs.call(parent) path_flow = Float::INFINITY v = sink while v != source u = parent[v] path_flow = [path_flow, graph[u][v]].min v = u end flow += path_flow v = sink while v != source u = parent[v] graph[u][v] -= path_flow graph[v][u] += path_flow v = u end end flow end
// PHP function maxFlow(array &$graph, int $source, int $sink, int $n): int { $bfs = function (array &$parent) use (&$graph, $source, $sink, $n): bool { $visited = array_fill(0, $n, false); $visited[$source] = true; $queue = [$source]; while (!empty($queue)) { $u = array_shift($queue); for ($v = 0; $v < $n; $v++) { if (!$visited[$v] && $graph[$u][$v] > 0) { $visited[$v] = true; $parent[$v] = $u; if ($v === $sink) return true; $queue[] = $v; } } } return false; }; $flow = 0; while (true) { $parent = array_fill(0, $n, -1); if (!$bfs($parent)) break; $pathFlow = PHP_INT_MAX; for ($v = $sink; $v !== $source; $v = $parent[$v]) $pathFlow = min($pathFlow, $graph[$parent[$v]][$v]); $flow += $pathFlow; for ($v = $sink; $v !== $source; $v = $parent[$v]) { $u = $parent[$v]; $graph[$u][$v] -= $pathFlow; $graph[$v][$u] += $pathFlow; } } return $flow; }
Time and Space Complexity
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Ford-Fulkerson (DFS) | O(E · max_flow) | O(V + E) | Bad on large integer capacities |
| Edmonds-Karp (BFS) | O(VE²) | O(V²) with adj matrix | Polynomial, preferred default |
| Dinic's algorithm | O(V²E) | O(V + E) | Faster in practice, uses level graphs |
| Push-relabel | O(V²√E) | O(V + E) | Best asymptotic for dense graphs |
For most interview problems, Edmonds-Karp is the right choice. The O(VE²) bound is polynomial, and V and E are both small in typical contest inputs (V ≤ 500, E ≤ 5000). The maximum flow algorithm guide covers Dinic's and push-relabel if you need them.
Space is dominated by the residual graph. An adjacency matrix takes O(V²). Switch to an adjacency list where each edge stores its reverse index and you get O(V + E), which matters for very sparse graphs.
Why You Got a Free Theorem
The max-flow min-cut result converts network problems into partition problems and back. That is a bigger deal than it sounds.
Maximum bipartite matching. Given a bipartite graph, the maximum matching (largest set of edges sharing no endpoints) equals the minimum vertex cover (smallest set of vertices touching every edge). This is König's theorem, and it falls directly from max-flow min-cut. Add a super-source connected to all left nodes and a super-sink connected to all right nodes, all edges capacity 1. The max flow gives the max matching. The min cut gives the min vertex cover. One algorithm, two answers.
Network reliability. What is the minimum number of edges you must cut to disconnect two nodes? Run max flow with every edge at capacity 1. The min cut is your answer. This is why the theorem shows up in infrastructure planning, circuit design, and image segmentation.
Image segmentation. Pixels are nodes. Adjacent pixels have edges weighted by color similarity. Source is "foreground," sink is "background." The min cut separates them at minimal cost. This is an actual production use case, not a toy problem from a textbook.
How Max Flow Disguises Itself in Your Interview
Max flow problems almost never introduce themselves as max flow problems. They show up wearing disguises, and missing the pattern costs you the problem.
"Maximum number of independent paths": how many vertex-disjoint or edge-disjoint paths exist from A to B? Set all edge capacities to 1 (or split vertices for vertex-disjoint). The max flow is the answer.
"Minimum number of nodes to remove to disconnect": vertex connectivity. Split each node v into v_in and v_out with edge capacity 1 between them. All other edges get capacity infinity. The min cut now counts the minimum vertex removals.
"Project selection / task dependency": some tasks have profit, some have cost, dependencies are constraints. This is a classic min-cut formulation. Source connects to profitable tasks, sink connects to costly ones, dependencies add directed edges. Max profit minus min cut gives the answer.
Bipartite matching problems: "assign workers to tasks," "match students to dorms," "route packets to servers." If the assignment has a capacity constraint, it maps directly to max flow.
The signal is a network with limits, a source and sink you can identify, and a question about maximum throughput or minimum separation. If that describes your problem, reach for max flow.
Flow problems trip people up in interviews because the disguise is convincing. If you want to practice spotting the pattern under pressure with voice-based feedback, SpaceComplexity has them in the problem set.
Two Bugs That Will Haunt You
Forgetting to initialize reverse edges. The residual graph needs graph[v][u] += capacity for every edge you add. If you only add forward edges, the algorithm cannot undo choices and will undercount the max flow. When you add edge (u, v) with capacity c, always also add (v, u) with capacity 0. Always. Without exception.
Using the wrong data structure for BFS. Ford-Fulkerson with DFS is not Edmonds-Karp. DFS can produce non-shortest paths. On adversarial inputs it degenerates to O(E · max_flow), which for large capacities means you are writing code that will never finish. Use a proper FIFO queue for BFS, not a stack. Your future self will thank you.