Data Structures & AlgorithmsNetwork Flow

Network Flow — Conceptual Introduction

LevelAdvanced

Duration90 mins

TopicNetwork Flow

4 / 5

The Max-Flow Min-Cut Theorem — Duality in Optimization

When Maximum Equals Minimum — A Profound Duality

In mathematics, the most beautiful theorems often reveal unexpected connections between seemingly unrelated concepts. The Max-Flow Min-Cut Theorem is one such gem—it states that the maximum flow in a network exactly equals the minimum capacity needed to completely disconnect the source from the sink.

This duality is not merely elegant; it's extraordinarily useful. It transforms questions about flow into questions about connectivity. It provides a certificate of optimality. And it underlies countless algorithms and problem reductions across computer science.

What You'll Master

By the end of this page, you'll understand: what a cut is and how to measure its capacity, why max-flow ≤ min-cut (the easy direction), why max-flow ≥ min-cut when no augmenting path exists (the hard direction), how this theorem proves Ford-Fulkerson's correctness, and practical applications of the duality perspective.

What is a Cut? — Partitioning the Network

Before stating the theorem, we need a precise understanding of cuts.

Definition — s-t Cut:

An s-t cut (or simply "cut") of a flow network G = (V, E) is a partition of V into two disjoint sets S and T such that:

s ∈ S (source is in S)
t ∈ T (sink is in T)
S ∪ T = V and S ∩ T = ∅

Intuitively, a cut is a way of dividing the network so that the source and sink are on opposite sides. The "cut" itself consists of all edges crossing from S to T.

Definition — Capacity of a Cut:

The capacity of a cut (S, T) is the sum of capacities of all edges going from S to T:

$$c(S, T) = \sum_{u \in S, v \in T} c(u, v)$$

Important: Only edges from S to T count. Edges from T to S (going "backward" across the cut) do NOT contribute to cut capacity.

Definition — Minimum Cut:

A minimum cut is an s-t cut with the smallest capacity among all possible s-t cuts:

$$\min_{(S,T) \text{ is s-t cut}} c(S, T)$$

The Asymmetry of Cut Capacity

Cut capacity only counts edges in the forward direction (S → T). If there's a high-capacity edge from T to S, it doesn't increase the cut capacity. This asymmetry mirrors the fact that flow goes from source to sink, not backward.

Visual Example:

        [A]----4---->[C]
       ↗ |          ↗ ↘
      3  |         2   5
     ↗   |2       ↗     ↘
  [S]    |      [D]      [T]
     ↘   ↓     ↗   ↘    ↗
      4  |    3     1   3
       ↘ |   ↗       ↘ ↗
        [B]----6---->[E]

Example Cut 1: S = {S, A}, T = {B, C, D, E, T}

Edges from S to T: S→B (4), A→C (4), A→B (2)
Cut capacity: 4 + 4 + 2 = 10

Example Cut 2: S = {S, A, B, D}, T = {C, E, T}

Edges from S to T: A→C (4), D→E (1), D→T (—wait, no direct edge), B→E (6)
Cut capacity: 4 + 1 + 6 = 11

Different cuts have different capacities. The minimum cut is the cheapest way to "disconnect" the network.

The Intuition — Why Cuts Limit Flow

Here's the key intuition: every unit of flow from s to t must cross every s-t cut.

Imagine the cut as a fence separating two regions. The source is on one side; the sink is on the other. Any flow from source to sink must pass through the fence. The total flow is therefore limited by the fence's capacity—how much can pass through.

The Bottleneck Principle for Cuts:

If any cut has capacity C, then the maximum flow cannot exceed C. Flow can't teleport past the cut; it must traverse the cut edges.

The Weakest Link

Think of cuts like security checkpoints. All traffic must pass through at least one checkpoint. The maximum traffic the system can handle is limited by the checkpoint with the smallest capacity. The minimum cut is that weakest checkpoint.

Formal Statement:

For any flow f and any cut (S, T):

$$|f| \leq c(S, T)$$

The flow value is at most the cut capacity.

Proof Sketch:

The value of flow |f| equals the net flow leaving S:

$$|f| = \sum_{u \in S, v \in T} f(u, v) - \sum_{u \in T, v \in S} f(u, v)$$

(Flow leaving S minus flow entering S from T)

Since f(u, v) ≤ c(u, v) for all edges, and flow is non-negative:

$$|f| \leq \sum_{u \in S, v \in T} c(u, v) - 0 = c(S, T)$$

Thus, every cut provides an upper bound on the maximum flow.

The Key Implication:

Since max flow ≤ every cut's capacity:

$$\max |f| \leq \min c(S, T)$$

The maximum flow is at most the minimum cut. This is the weak duality—the "easy" direction of Max-Flow Min-Cut.

The profound insight is that this inequality is actually an equality. The maximum flow doesn't just stay below the minimum cut—it exactly achieves it.

The Theorem — Equality Holds

The Max-Flow Min-Cut Theorem (Ford-Fulkerson, 1956):

In any flow network, the following three conditions are equivalent:

f is a maximum flow (no flow has larger value)
The residual graph G_f has no augmenting path from s to t
|f| = c(S, T) for some s-t cut (S, T)

The Grand Statement:

$$\max_{\text{flow } f} |f| = \min_{\text{cut } (S,T)} c(S, T)$$

The maximum flow value exactly equals the minimum cut capacity.

The Triple Equivalence

These three conditions being equivalent is powerful. (1→2) says we can detect optimality by checking for augmenting paths. (2→3) says absence of paths implies we've hit a cut ceiling. (3→1) says achieving cut capacity means we're optimal. The circular proof connects algorithmic termination to theoretical optimality.

Why This Is Remarkable:

Algorithmic Verification: To prove a flow f is maximum, we don't need to check all other flows. We just verify no augmenting path exists—a polynomial-time check.
Certificate of Optimality: The minimum cut serves as a "proof" that the flow is optimal. If someone claims a larger flow is possible, show them the cut—flow can't exceed cut capacity.
Problem Duality: Maximizing flow and minimizing cuts are "dual" problems. Solving one solves the other. This is a special case of linear programming duality.
Structural Insight: The minimum cut reveals the network's bottleneck—which edges, if upgraded, would increase maximum throughput.

Proof of the Theorem — Completing the Circle

We prove the equivalence by showing: (1) → (2) → (3) → (1).

Proof of (1) → (2): Maximum flow implies no augmenting path

Contradiction: Suppose f is maximum but an augmenting path p exists in G_f.

Let Δ = min residual capacity along p (this is positive)
We can create flow f' by augmenting f along p
|f'| = |f| + Δ > |f|
This contradicts f being maximum

Therefore, maximum flow means no augmenting path. ✓

Proof of (2) → (3): No augmenting path implies flow equals some cut

This is the key step. Define:

S = {v ∈ V : v is reachable from s in residual graph G_f}
T = V - S

Since no augmenting path exists, t ∉ S (t is not reachable from s in G_f). So s ∈ S and t ∈ T, making (S, T) a valid s-t cut.

Claim: For this cut, |f| = c(S, T).

Proof of claim:

Consider any edge (u, v) with u ∈ S and v ∈ T:

Since v is not reachable from s but u is, the edge (u, v) has zero residual capacity in G_f
This means f(u, v) = c(u, v) — the edge is saturated

Consider any edge (u, v) with u ∈ T and v ∈ S:

If f(u, v) > 0, there would be a backward edge (v, u) in G_f with positive capacity
Since v ∈ S (reachable from s), u would also be reachable via this edge
But u ∈ T, contradiction. So f(u, v) = 0

Now compute: $$|f| = \sum_{u \in S, v \in T} f(u,v) - \sum_{u \in T, v \in S} f(u,v) = \sum_{u \in S, v \in T} c(u,v) - 0 = c(S,T)$$

Thus |f| = c(S, T). ✓

Proof of (3) → (1): Flow equals cut capacity implies maximum

We already proved |f| ≤ c(S', T') for ANY cut (S', T').

If |f| = c(S, T) for some specific cut, then:

|f| ≤ min over all cuts of c(S', T')
But |f| = c(S, T) ≥ min c(S', T')
Therefore |f| = min c(S', T')

Since no flow can exceed any cut, and f equals the minimum cut, f must be maximum. ✓

The Circle is Complete:

(1) ↔ (2) ↔ (3) ↔ (1)

All three conditions are equivalent, and importantly, max flow = min cut. ∎

The Constructive Cut

The proof of (2) → (3) is constructive: it tells us HOW to find a minimum cut once we have maximum flow. Simply run BFS/DFS from s in the residual graph. Reachable vertices form S; unreachable form T. The edges crossing from S to T (in the original graph, saturated) constitute the minimum cut.

Finding the Minimum Cut — A Practical Algorithm

The theorem provides an algorithm for finding minimum cuts:

Algorithm: Find Minimum s-t Cut
1. Compute maximum flow f using Ford-Fulkerson/Edmonds-Karp
2. Construct the residual graph G_f
3. Find S = all vertices reachable from s in G_f (using BFS/DFS)
4. Let T = V - S
5. The minimum cut is (S, T)
6. The cut edges are: {(u, v) ∈ E : u ∈ S, v ∈ T}

This runs in the same time as finding maximum flow, plus O(V + E) for the final BFS/DFS.

min_cut.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
from collections import deque
 
def find_min_cut(graph, source, sink, max_flow_value, flow):
    """
    Find the minimum s-t cut after computing maximum flow.
    
    Args:
        graph: Original graph with capacities
        source: Source vertex
        sink: Sink vertex  
        max_flow_value: The maximum flow value (for reference)
        flow: The flow assignment from max flow algorithm
    
    Returns:
        Tuple of (S, T, cut_edges, cut_capacity)
    """
    # Build residual graph
    def residual_capacity(u, v):
        cap = graph.get(u, {}).get(v, 0)
        f = flow.get(u, {}).get(v, 0)
        return cap - f  # Forward residual
    
    def backward_capacity(u, v):
        return flow.get(v, {}).get(u, 0)  # Backward residual
    
    # BFS to find all vertices reachable from source in residual graph
    S = set()
    visited = {source}
    queue = deque([source])
    
    while queue:
        u = queue.popleft()
        S.add(u)
        
        # Check forward edges
        for v in graph.get(u, {}):
            if v not in visited and residual_capacity(u, v) > 0:
                visited.add(v)
                queue.append(v)
        
        # Check backward edges (from any v where flow[v][u] > 0)
        for v in graph:
            if v not in visited and backward_capacity(u, v) > 0:
                visited.add(v)
                queue.append(v)
    
    # T is everything not in S
    all_vertices = set(graph.keys())
    for u in graph:
        for v in graph[u]:
            all_vertices.add(v)
    T = all_vertices - S
    
    # Find cut edges and capacity
    cut_edges = []
    cut_capacity = 0
    for u in S:
        for v, cap in graph.get(u, {}).items():
            if v in T:
                cut_edges.append((u, v, cap))
                cut_capacity += cap
    
    return S, T, cut_edges, cut_capacity
 
 
# Example usage
graph = {
    'S': {'A': 10, 'B': 10},
    'A': {'B': 2, 'T': 10},
    'B': {'T': 10},
    'T': {}
}
 
# Assume we already computed max flow = 20
# with flow: S->A: 10, S->B: 10, A->B: 0, A->T: 10, B->T: 10
flow = {
    'S': {'A': 10, 'B': 10},
    'A': {'B': 0, 'T': 10},
    'B': {'T': 10}
}
 
S, T, cut_edges, cut_cap = find_min_cut(graph, 'S', 'T', 20, flow)
print(f"S = {S}")           # {'S'}
print(f"T = {T}")           # {'A', 'B', 'T'}
print(f"Cut edges: {cut_edges}")  # [('S', 'A', 10), ('S', 'B', 10)]
print(f"Min cut capacity: {cut_cap}")  # 20 (equals max flow!)

Multiple Minimum Cuts May Exist

There may be multiple minimum cuts with the same capacity. The algorithm finds ONE of them—specifically, the one where S contains all vertices reachable from source. Other minimum cuts might exist with different S-T partitions.

Applications of the Duality

The max-flow min-cut duality has profound applications beyond computing flow values.

Practical Applications of Max-Flow Min-Cut

•Network Reliability Analysis: The minimum cut identifies the most vulnerable points in a network. If those edges fail, the network is disconnected. Critical infrastructure planning uses this to identify single points of failure.
•Image Segmentation: In computer vision, pixels are nodes, and similarity between pixels determines edge weights. The minimum cut separates "foreground" from "background"—a clean partition that minimizes cross-boundary dissimilarity.
•Project Selection: Given projects with profits and dependencies, find the maximum profit subset. This reduces to min-cut: projects are nodes, dependencies are edges, and the cut separates selected from unselected.
•Bipartite Vertex Cover: König's theorem states that in bipartite graphs, the size of maximum matching equals minimum vertex cover. This is a consequence of max-flow min-cut.
•Clustering: Minimum cuts can partition graphs into clusters, minimizing the "cost" of edges cut. This is used in community detection and data clustering.

Example: Network Vulnerability

Consider a communication network connecting cities:

    [NYC]---5---[Chicago]---3---[Denver]
      |            |              |
      4            2              4
      |            |              |
    [DC]----3----[Dallas]---2---[LA]

To find the network's vulnerability between NYC (source) and LA (sink):

Compute max flow: limited by the minimum cut
The min cut edges are the critical links
If these links all fail, NYC cannot reach LA

Reinforcing the minimum cut edges increases overall network resilience.

Example: Image Segmentation

For a grayscale image:

Each pixel is a node
Source connects to "likely foreground" pixels (high intensity)
Sink connects to "likely background" pixels (low intensity)
Adjacent pixels have edges weighted by similarity

The minimum cut separates foreground from background, minimizing the perimeter cost while respecting intensity cues.

The Power of Duality Thinking

Often it's easier to think about cuts than flows. 'What's the cheapest way to disconnect x from y?' is sometimes more intuitive than 'What's the maximum flow from x to y?' The theorem says these questions have the same answer.

The Flow Across Any Cut — A Useful Lemma

A useful consequence of flow conservation is that the net flow across ANY s-t cut equals the flow value.

Lemma: For any flow f and any s-t cut (S, T):

$$|f| = \sum_{u \in S, v \in T} f(u,v) - \sum_{u \in T, v \in S} f(u,v)$$

The flow value equals "forward flow across cut" minus "backward flow across cut."

Proof Intuition:

By flow conservation, at each intermediate vertex, flow in = flow out. Sum this over all vertices in S (except for source, which has extra outflow = |f|):

$$|f| + \sum_{v \in S-{s}} (\text{flow in to } v) = \sum_{v \in S-{s}} (\text{flow out of } v) + \text{extra}$$

The internal edges (within S) cancel. What remains is exactly the net flow crossing from S to T.

Why This Matters:

Any cut works: We can compute flow value by examining net flow across ANY cut, not just at the source or sink. This flexibility is useful in proofs and algorithms.
Bounding max flow: For any cut, net flow across it is at most the cut capacity. This immediately gives max flow ≤ min cut.
Identifying saturated cuts: When net flow equals cut capacity, we've found both the maximum flow and a minimum cut simultaneously.

Example:

    [S]---5/10--->[A]---3/5--->[B]---3/3--->[T]
              \       /-2/2
               \     /
              5/6---[C]---2/4--->/

Suppose we have flow value 8 entering T (3 from B, 5 from C).

Cut 1: S = {S}, T = {A, B, C, T}

Forward: 5 + 5 = 10? No, we need actual flow not capacity
Forward flow: f(S,A)=5, f(S,C)=5 → 10
Wait, that's more than 8. Let me reconsider.

Actually, with proper flow values that sum to 8 at T, any cut would give 8 as net flow. The lemma guarantees consistency.

Consistency Check

If your flow computation gives different values when measured at different cuts, there's a bug. This lemma provides a way to validate flow computations: measure flow value at multiple cuts and verify they agree.

Relationship to Linear Programming

The max-flow min-cut theorem is a special case of linear programming duality. Understanding this connection provides deeper insight.

Max Flow as a Linear Program:

Maximize: $\sum_{v} f(s, v)$ (total flow out of source)

Subject to:

$0 \leq f(u, v) \leq c(u, v)$ for all edges (capacity constraints)
$\sum_u f(u, v) = \sum_w f(v, w)$ for all $v \neq s, t$ (conservation)

This is a linear program: linear objective, linear constraints.

The Dual Linear Program:

The dual of max flow turns out to be... min cut! (with some technical formulation details)

By LP duality theory, the optimal values of primal and dual are equal when both are feasible. This is exactly max-flow = min-cut.

Why This Matters

If you know LP duality, max-flow min-cut becomes 'obvious'—it's just the duality theorem applied to a specific LP. Conversely, if you understand max-flow min-cut intuitively, it gives concrete intuition for the abstract LP duality theorem.

Integrality Property:

A beautiful consequence: if all capacities are integers, there exists an integer-valued maximum flow.

This follows because:

The constraint matrix of the max flow LP is totally unimodular
For TU matrices, LP solutions are integral when right-hand sides are integral
Capacities (the RHS) are integers → optimal flow values are integers

Practical Impact:

This integrality is crucial for matching problems. When we reduce bipartite matching to max flow with capacity 1 edges, the max flow value (an integer) equals the maximum matching size. No rounding needed—the LP relaxation is exact.

Max Flow LP and Its Dual
Aspect	Primal (Max Flow)	Dual (Min Cut)
Objective	Maximize flow value	Minimize cut capacity
Variables	Flow on each edge	Indicator: vertex in S or T
Constraints	Capacity, conservation	Cut edges must cover all paths
Optimal value	Maximum flow	Minimum cut capacity
Relationship	Primal optimal = Dual optimal	By LP duality theorem

Summary and Preview

The Max-Flow Min-Cut theorem is one of the crown jewels of combinatorial optimization. Let's consolidate what we've learned:

Key Takeaways

•An s-t cut partitions vertices with source on one side, sink on the other. Cut capacity = sum of crossing edge capacities.
•Weak duality: Max flow ≤ every cut capacity, hence max flow ≤ min cut. Every cut is an upper bound.
•Strong duality (the theorem): Max flow = min cut. The inequality is tight.
•Three equivalent conditions: Maximum flow ↔ no augmenting path ↔ achieves some cut's capacity.
•The proof is constructive: After max flow, reachable vertices in residual graph form S of the min cut.
•Applications abound: Network reliability, image segmentation, project selection, clustering, and more use this duality.
•LP perspective: Max-flow min-cut is LP duality for a specific totally unimodular program.

What's Next:

We've built the theoretical foundation of network flow. Now it's time to see these concepts in action through real-world applications. The final page explores bipartite matching, resource allocation, and other problems that reduce elegantly to maximum flow—demonstrating why mastering network flow gives you a powerful problem-solving tool.

Duality Mastered

You now understand one of the most beautiful results in theoretical computer science. The max-flow min-cut theorem connects optimization (finding best flow) with combinatorics (finding weakest cut). This duality perspective will serve you well across many algorithmic domains.

4 / 5

Loading learning content...

Data Structures & AlgorithmsNetwork Flow

Network Flow — Conceptual Introduction

LevelAdvanced

Duration90 mins

TopicNetwork Flow

4 / 5

The Max-Flow Min-Cut Theorem — Duality in Optimization

When Maximum Equals Minimum — A Profound Duality

What You'll Master

What is a Cut? — Partitioning the Network

Before stating the theorem, we need a precise understanding of cuts.

Definition — s-t Cut:

An s-t cut (or simply "cut") of a flow network G = (V, E) is a partition of V into two disjoint sets S and T such that:

s ∈ S (source is in S)
t ∈ T (sink is in T)
S ∪ T = V and S ∩ T = ∅

Intuitively, a cut is a way of dividing the network so that the source and sink are on opposite sides. The "cut" itself consists of all edges crossing from S to T.

Definition — Capacity of a Cut:

The capacity of a cut (S, T) is the sum of capacities of all edges going from S to T:

$$c(S, T) = \sum_{u \in S, v \in T} c(u, v)$$

Important: Only edges from S to T count. Edges from T to S (going "backward" across the cut) do NOT contribute to cut capacity.

Definition — Minimum Cut:

A minimum cut is an s-t cut with the smallest capacity among all possible s-t cuts:

$$\min_{(S,T) \text{ is s-t cut}} c(S, T)$$

The Asymmetry of Cut Capacity

Visual Example:

        [A]----4---->[C]
       ↗ |          ↗ ↘
      3  |         2   5
     ↗   |2       ↗     ↘
  [S]    |      [D]      [T]
     ↘   ↓     ↗   ↘    ↗
      4  |    3     1   3
       ↘ |   ↗       ↘ ↗
        [B]----6---->[E]

Example Cut 1: S = {S, A}, T = {B, C, D, E, T}

Edges from S to T: S→B (4), A→C (4), A→B (2)
Cut capacity: 4 + 4 + 2 = 10

Example Cut 2: S = {S, A, B, D}, T = {C, E, T}

Edges from S to T: A→C (4), D→E (1), D→T (—wait, no direct edge), B→E (6)
Cut capacity: 4 + 1 + 6 = 11

Different cuts have different capacities. The minimum cut is the cheapest way to "disconnect" the network.

The Intuition — Why Cuts Limit Flow

Here's the key intuition: every unit of flow from s to t must cross every s-t cut.

The Bottleneck Principle for Cuts:

If any cut has capacity C, then the maximum flow cannot exceed C. Flow can't teleport past the cut; it must traverse the cut edges.

The Weakest Link

Formal Statement:

For any flow f and any cut (S, T):

$$|f| \leq c(S, T)$$

The flow value is at most the cut capacity.

Proof Sketch:

The value of flow |f| equals the net flow leaving S:

$$|f| = \sum_{u \in S, v \in T} f(u, v) - \sum_{u \in T, v \in S} f(u, v)$$

(Flow leaving S minus flow entering S from T)

Since f(u, v) ≤ c(u, v) for all edges, and flow is non-negative:

$$|f| \leq \sum_{u \in S, v \in T} c(u, v) - 0 = c(S, T)$$

Thus, every cut provides an upper bound on the maximum flow.

The Key Implication:

Since max flow ≤ every cut's capacity:

$$\max |f| \leq \min c(S, T)$$

The maximum flow is at most the minimum cut. This is the weak duality—the "easy" direction of Max-Flow Min-Cut.

The profound insight is that this inequality is actually an equality. The maximum flow doesn't just stay below the minimum cut—it exactly achieves it.

The Theorem — Equality Holds

The Max-Flow Min-Cut Theorem (Ford-Fulkerson, 1956):

In any flow network, the following three conditions are equivalent:

f is a maximum flow (no flow has larger value)
The residual graph G_f has no augmenting path from s to t
|f| = c(S, T) for some s-t cut (S, T)

The Grand Statement:

$$\max_{\text{flow } f} |f| = \min_{\text{cut } (S,T)} c(S, T)$$

The maximum flow value exactly equals the minimum cut capacity.

The Triple Equivalence

Why This Is Remarkable:

Algorithmic Verification: To prove a flow f is maximum, we don't need to check all other flows. We just verify no augmenting path exists—a polynomial-time check.
Certificate of Optimality: The minimum cut serves as a "proof" that the flow is optimal. If someone claims a larger flow is possible, show them the cut—flow can't exceed cut capacity.
Problem Duality: Maximizing flow and minimizing cuts are "dual" problems. Solving one solves the other. This is a special case of linear programming duality.
Structural Insight: The minimum cut reveals the network's bottleneck—which edges, if upgraded, would increase maximum throughput.

Proof of the Theorem — Completing the Circle

We prove the equivalence by showing: (1) → (2) → (3) → (1).

Proof of (1) → (2): Maximum flow implies no augmenting path

Contradiction: Suppose f is maximum but an augmenting path p exists in G_f.

Let Δ = min residual capacity along p (this is positive)
We can create flow f' by augmenting f along p
|f'| = |f| + Δ > |f|
This contradicts f being maximum

Therefore, maximum flow means no augmenting path. ✓

Proof of (2) → (3): No augmenting path implies flow equals some cut

This is the key step. Define:

S = {v ∈ V : v is reachable from s in residual graph G_f}
T = V - S

Since no augmenting path exists, t ∉ S (t is not reachable from s in G_f). So s ∈ S and t ∈ T, making (S, T) a valid s-t cut.

Claim: For this cut, |f| = c(S, T).

Proof of claim:

Consider any edge (u, v) with u ∈ S and v ∈ T:

Since v is not reachable from s but u is, the edge (u, v) has zero residual capacity in G_f
This means f(u, v) = c(u, v) — the edge is saturated

Consider any edge (u, v) with u ∈ T and v ∈ S:

If f(u, v) > 0, there would be a backward edge (v, u) in G_f with positive capacity
Since v ∈ S (reachable from s), u would also be reachable via this edge
But u ∈ T, contradiction. So f(u, v) = 0

Now compute: $$|f| = \sum_{u \in S, v \in T} f(u,v) - \sum_{u \in T, v \in S} f(u,v) = \sum_{u \in S, v \in T} c(u,v) - 0 = c(S,T)$$

Thus |f| = c(S, T). ✓

Proof of (3) → (1): Flow equals cut capacity implies maximum

We already proved |f| ≤ c(S', T') for ANY cut (S', T').

If |f| = c(S, T) for some specific cut, then:

|f| ≤ min over all cuts of c(S', T')
But |f| = c(S, T) ≥ min c(S', T')
Therefore |f| = min c(S', T')

Since no flow can exceed any cut, and f equals the minimum cut, f must be maximum. ✓

The Circle is Complete:

(1) ↔ (2) ↔ (3) ↔ (1)

All three conditions are equivalent, and importantly, max flow = min cut. ∎

The Constructive Cut

Finding the Minimum Cut — A Practical Algorithm

The theorem provides an algorithm for finding minimum cuts:

Algorithm: Find Minimum s-t Cut
1. Compute maximum flow f using Ford-Fulkerson/Edmonds-Karp
2. Construct the residual graph G_f
3. Find S = all vertices reachable from s in G_f (using BFS/DFS)
4. Let T = V - S
5. The minimum cut is (S, T)
6. The cut edges are: {(u, v) ∈ E : u ∈ S, v ∈ T}

This runs in the same time as finding maximum flow, plus O(V + E) for the final BFS/DFS.

min_cut.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
from collections import deque
 
def find_min_cut(graph, source, sink, max_flow_value, flow):
    """
    Find the minimum s-t cut after computing maximum flow.
    
    Args:
        graph: Original graph with capacities
        source: Source vertex
        sink: Sink vertex  
        max_flow_value: The maximum flow value (for reference)
        flow: The flow assignment from max flow algorithm
    
    Returns:
        Tuple of (S, T, cut_edges, cut_capacity)
    """
    # Build residual graph
    def residual_capacity(u, v):
        cap = graph.get(u, {}).get(v, 0)
        f = flow.get(u, {}).get(v, 0)
        return cap - f  # Forward residual
    
    def backward_capacity(u, v):
        return flow.get(v, {}).get(u, 0)  # Backward residual
    
    # BFS to find all vertices reachable from source in residual graph
    S = set()
    visited = {source}
    queue = deque([source])
    
    while queue:
        u = queue.popleft()
        S.add(u)
        
        # Check forward edges
        for v in graph.get(u, {}):
            if v not in visited and residual_capacity(u, v) > 0:
                visited.add(v)
                queue.append(v)
        
        # Check backward edges (from any v where flow[v][u] > 0)
        for v in graph:
            if v not in visited and backward_capacity(u, v) > 0:
                visited.add(v)
                queue.append(v)
    
    # T is everything not in S
    all_vertices = set(graph.keys())
    for u in graph:
        for v in graph[u]:
            all_vertices.add(v)
    T = all_vertices - S
    
    # Find cut edges and capacity
    cut_edges = []
    cut_capacity = 0
    for u in S:
        for v, cap in graph.get(u, {}).items():
            if v in T:
                cut_edges.append((u, v, cap))
                cut_capacity += cap
    
    return S, T, cut_edges, cut_capacity
 
 
# Example usage
graph = {
    'S': {'A': 10, 'B': 10},
    'A': {'B': 2, 'T': 10},
    'B': {'T': 10},
    'T': {}
}
 
# Assume we already computed max flow = 20
# with flow: S->A: 10, S->B: 10, A->B: 0, A->T: 10, B->T: 10
flow = {
    'S': {'A': 10, 'B': 10},
    'A': {'B': 0, 'T': 10},
    'B': {'T': 10}
}
 
S, T, cut_edges, cut_cap = find_min_cut(graph, 'S', 'T', 20, flow)
print(f"S = {S}")           # {'S'}
print(f"T = {T}")           # {'A', 'B', 'T'}
print(f"Cut edges: {cut_edges}")  # [('S', 'A', 10), ('S', 'B', 10)]
print(f"Min cut capacity: {cut_cap}")  # 20 (equals max flow!)

Multiple Minimum Cuts May Exist

Applications of the Duality

The max-flow min-cut duality has profound applications beyond computing flow values.

Practical Applications of Max-Flow Min-Cut

•Network Reliability Analysis: The minimum cut identifies the most vulnerable points in a network. If those edges fail, the network is disconnected. Critical infrastructure planning uses this to identify single points of failure.
•Image Segmentation: In computer vision, pixels are nodes, and similarity between pixels determines edge weights. The minimum cut separates "foreground" from "background"—a clean partition that minimizes cross-boundary dissimilarity.
•Project Selection: Given projects with profits and dependencies, find the maximum profit subset. This reduces to min-cut: projects are nodes, dependencies are edges, and the cut separates selected from unselected.
•Bipartite Vertex Cover: König's theorem states that in bipartite graphs, the size of maximum matching equals minimum vertex cover. This is a consequence of max-flow min-cut.
•Clustering: Minimum cuts can partition graphs into clusters, minimizing the "cost" of edges cut. This is used in community detection and data clustering.

Example: Network Vulnerability

Consider a communication network connecting cities:

    [NYC]---5---[Chicago]---3---[Denver]
      |            |              |
      4            2              4
      |            |              |
    [DC]----3----[Dallas]---2---[LA]

To find the network's vulnerability between NYC (source) and LA (sink):

Compute max flow: limited by the minimum cut
The min cut edges are the critical links
If these links all fail, NYC cannot reach LA

Reinforcing the minimum cut edges increases overall network resilience.

Example: Image Segmentation

For a grayscale image:

Each pixel is a node
Source connects to "likely foreground" pixels (high intensity)
Sink connects to "likely background" pixels (low intensity)
Adjacent pixels have edges weighted by similarity

The minimum cut separates foreground from background, minimizing the perimeter cost while respecting intensity cues.

The Power of Duality Thinking

The Flow Across Any Cut — A Useful Lemma

A useful consequence of flow conservation is that the net flow across ANY s-t cut equals the flow value.

Lemma: For any flow f and any s-t cut (S, T):

$$|f| = \sum_{u \in S, v \in T} f(u,v) - \sum_{u \in T, v \in S} f(u,v)$$

The flow value equals "forward flow across cut" minus "backward flow across cut."

Proof Intuition:

By flow conservation, at each intermediate vertex, flow in = flow out. Sum this over all vertices in S (except for source, which has extra outflow = |f|):

$$|f| + \sum_{v \in S-{s}} (\text{flow in to } v) = \sum_{v \in S-{s}} (\text{flow out of } v) + \text{extra}$$

The internal edges (within S) cancel. What remains is exactly the net flow crossing from S to T.

Why This Matters:

Any cut works: We can compute flow value by examining net flow across ANY cut, not just at the source or sink. This flexibility is useful in proofs and algorithms.
Bounding max flow: For any cut, net flow across it is at most the cut capacity. This immediately gives max flow ≤ min cut.
Identifying saturated cuts: When net flow equals cut capacity, we've found both the maximum flow and a minimum cut simultaneously.

Example:

    [S]---5/10--->[A]---3/5--->[B]---3/3--->[T]
              \       /-2/2
               \     /
              5/6---[C]---2/4--->/

Suppose we have flow value 8 entering T (3 from B, 5 from C).

Cut 1: S = {S}, T = {A, B, C, T}

Forward: 5 + 5 = 10? No, we need actual flow not capacity
Forward flow: f(S,A)=5, f(S,C)=5 → 10
Wait, that's more than 8. Let me reconsider.

Actually, with proper flow values that sum to 8 at T, any cut would give 8 as net flow. The lemma guarantees consistency.

Consistency Check

Relationship to Linear Programming

The max-flow min-cut theorem is a special case of linear programming duality. Understanding this connection provides deeper insight.

Max Flow as a Linear Program:

Maximize: $\sum_{v} f(s, v)$ (total flow out of source)

Subject to:

$0 \leq f(u, v) \leq c(u, v)$ for all edges (capacity constraints)
$\sum_u f(u, v) = \sum_w f(v, w)$ for all $v \neq s, t$ (conservation)

This is a linear program: linear objective, linear constraints.

The Dual Linear Program:

The dual of max flow turns out to be... min cut! (with some technical formulation details)

By LP duality theory, the optimal values of primal and dual are equal when both are feasible. This is exactly max-flow = min-cut.

Why This Matters

Integrality Property:

A beautiful consequence: if all capacities are integers, there exists an integer-valued maximum flow.

This follows because:

The constraint matrix of the max flow LP is totally unimodular
For TU matrices, LP solutions are integral when right-hand sides are integral
Capacities (the RHS) are integers → optimal flow values are integers

Practical Impact:

Max Flow LP and Its Dual
Aspect	Primal (Max Flow)	Dual (Min Cut)
Objective	Maximize flow value	Minimize cut capacity
Variables	Flow on each edge	Indicator: vertex in S or T
Constraints	Capacity, conservation	Cut edges must cover all paths
Optimal value	Maximum flow	Minimum cut capacity
Relationship	Primal optimal = Dual optimal	By LP duality theorem

Summary and Preview

The Max-Flow Min-Cut theorem is one of the crown jewels of combinatorial optimization. Let's consolidate what we've learned:

Key Takeaways

•An s-t cut partitions vertices with source on one side, sink on the other. Cut capacity = sum of crossing edge capacities.
•Weak duality: Max flow ≤ every cut capacity, hence max flow ≤ min cut. Every cut is an upper bound.
•Strong duality (the theorem): Max flow = min cut. The inequality is tight.
•Three equivalent conditions: Maximum flow ↔ no augmenting path ↔ achieves some cut's capacity.
•The proof is constructive: After max flow, reachable vertices in residual graph form S of the min cut.
•Applications abound: Network reliability, image segmentation, project selection, clustering, and more use this duality.
•LP perspective: Max-flow min-cut is LP duality for a specific totally unimodular program.

What's Next:

Duality Mastered

4 / 5