Chapter 34: Network Flow and Matching

"The maximum flow through a network equals the minimum capacity of a cut that separates the source from the sink." — the max-flow min-cut theorem, proved independently by Ford & Fulkerson and by Elias, Feinstein & Shannon in 1956

Overview

You have a graph, and now you want to push something through it. Not just walk from one vertex to another — that was shortest paths, Chapter 29 — but route as much stuff as the edges can carry, all at once, from a starting point to a destination. The stuff might be data packets through a network of routers, oil through a pipeline, cars through a road grid, or, more abstractly, assignments: which delivery driver covers which route, which student gets which dorm room, which ad slot shows which campaign. Every one of these is the same mathematical object — a flow network — and the question "how much can I push?" has a single, beautiful, computable answer.

This chapter is the synthesis of everything you have learned about graphs. It uses weighted edges (Chapter 29), it traverses with the BFS you built in Chapter 28, it rests on a correctness argument with the same flavor as the greedy proofs you saw for minimum spanning trees in Chapter 32, and it pays off the social-network thread by answering a question pure connectivity cannot: not "can these people be matched?" but "what is the largest set of compatible pairs?" The centerpiece is one of the most celebrated results in all of combinatorial optimization — the max-flow min-cut theorem — which says that the most you can push (a maximization) is exactly equal to the cheapest way to sever the network (a minimization). Two problems that look like opposites turn out to be the same number. When a maximization and a minimization meet in the middle like that, something deep is going on, and you will see exactly why.

Here is the programmer's payoff. A startling range of problems that look nothing like plumbing — bipartite matching, project selection, baseball elimination, image segmentation, even some scheduling problems — can be reduced to max flow. Once you can recognize the flow inside a problem, you get an efficient algorithm for free. Learning to see flow networks where they are hiding is one of the highest-leverage modeling skills in this book.

In this chapter you will learn to:

• Model a transport or allocation problem as a flow network with capacities, a source, and a sink.
• State precisely what a valid flow is and what its value means.
• Run the Ford–Fulkerson method by hand, including the crucial trick of undoing flow along back edges in a residual network.
• Prove a flow is maximum by exhibiting a matching minimum cut — and understand why such a cut must always exist.
• Turn a bipartite-matching problem into a flow problem and read the matching back out.
• Spot flow and matching structure inside assignment, scheduling, and segmentation problems.

Learning Paths

🏃 Fast Track: If you only need the working knowledge, read §34.1 (the model), the statement of Ford–Fulkerson in §34.3, the statement of the max-flow min-cut theorem in §34.4 (skip its proof on a first pass), and the matching reduction in §34.5. Do the ⭐⭐ exercises and the Project Checkpoint.

📖 Standard Path: Read in order. Trace the Ford–Fulkerson example in §34.3 by hand on paper before reading our trace — getting the back-edge step right is the whole chapter. Work every 🔄 Check Your Understanding.

🔬 Deep Dive: Read the full max-flow min-cut proof in §34.4 and convince yourself each of its three implications. Then prove König's theorem from max-flow min-cut (§34.5), and read about Hall's marriage theorem and the augmenting-path view of matching in Further Reading.

34.1 Flow networks

Let's start with the picture, because the abstraction is just this picture made precise.

Imagine a system of water pipes. Water enters at one special junction called the source (label it $s$) and must leave at another called the sink (label it $t$). Each pipe is a one-way segment with a maximum throughput — a 4-inch pipe can carry only so many liters per second no matter how hard you push. At every junction other than the source and sink, water cannot accumulate or vanish: whatever flows in must flow out. Question: turn the source on full blast — what is the greatest total rate at which water can leave at the sink?

Here is a small concrete network. Each edge is labelled with its capacity — the most it can carry:

            10            4
       s --------> a --------> b
        \          |          /
       3 \         | 3       / 10
          \        v        v
           '-----> b? ...   t

That ASCII picture gets crowded fast, so let's write the network as a list of directed edges with capacities, which is also exactly how we'll store it in code. Our running example for this chapter, call it network $M$, has vertices $\{s, a, b, t\}$ and these capacities:

$$ c(s,a)=10,\quad c(s,b)=3,\quad c(a,b)=4,\quad c(a,t)=3,\quad c(b,t)=10. $$

Drawn cleanly:

        (10)        (4)
   s ----------> a ----------> b
   |             |             |
   | (3)         | (3)         | (10)
   |             v             v
   '----------> b ........... t
                (the s->b edge and a->t edge feed the lower path)

Read it as: a fat pipe $s\to a$ (capacity 10), a thin pipe $a\to b$ (capacity 4) and a side exit $a\to t$ (capacity 3); a modest pipe $s\to b$ (capacity 3) feeding into the big drain $b\to t$ (capacity 10). Intuitively, the fat $s\to a$ pipe promises a lot, but the thin $a\to b$ and the limited $a\to t$ form a bottleneck. Hold that intuition; we will pin down the exact maximum in §34.3 and prove it in §34.4.

Now the formal definition.

Definition (flow network). A flow network is a directed graph $G = (V, E)$ together with: - a capacity function $c\colon E \to \mathbb{R}_{\ge 0}$ assigning each edge $(u,v)$ a nonnegative number $c(u,v)$ (the most it can carry), and - two distinguished vertices: a source $s$ and a sink $t$, with $s \neq t$.

By convention, if $(u,v) \notin E$ we take $c(u,v) = 0$. We assume every vertex lies on some path from $s$ to $t$ (vertices that don't are irrelevant to flow).

🔗 Connection. A flow network is a weighted directed graph (Chapter 27) where the weights are reinterpreted: in Chapter 29 an edge weight was a cost to be minimized along a single path; here a weight is a capacity to be respected by an aggregate flow. Same data structure, completely different question. Recognizing that the same Graph object answers many different questions is the abstraction payoff (theme three).

What flows through the network is a flow — an assignment of an actual amount to each edge, subject to two rules.

Definition (flow). A flow in a network $G$ is a function $f\colon E \to \mathbb{R}_{\ge 0}$ satisfying: 1. Capacity constraint: for every edge $(u,v)$, $\ 0 \le f(u,v) \le c(u,v)$. (You cannot push more than a pipe can carry.) 2. Conservation constraint (flow conservation): for every vertex $v \neq s, t$, $$\sum_{u\,:\,(u,v)\in E} f(u,v) \;=\; \sum_{w\,:\,(v,w)\in E} f(v,w).$$ (At every internal junction, flow in equals flow out — nothing is created or stored.)

The value of the flow, written $\lvert f\rvert$, is the net flow out of the source: $$\lvert f\rvert \;=\; \sum_{w\,:\,(s,w)\in E} f(s,w) \;-\; \sum_{u\,:\,(u,s)\in E} f(u,s).$$ (In our examples the source has no incoming edges, so $\lvert f\rvert$ is just the total leaving $s$.)

A short sanity fact, worth stating because we will lean on it: the value also equals the net flow into the sink. This is just conservation summed over all internal vertices — whatever leaves the source and isn't stored anywhere must arrive at the sink. We will use this freely.

Here is one valid flow on network $M$ (we will discover it properly in §34.3; for now just verify it is legal):

$$ f(s,a)=7,\quad f(s,b)=3,\quad f(a,b)=4,\quad f(a,t)=3,\quad f(b,t)=7. $$

Let's check both constraints, because checking a flow is a skill you'll use constantly.

• Capacity: $7\le 10$, $3\le 3$, $4\le 4$, $3\le 3$, $7\le 10$. ✓ Every edge is within capacity (and three of them — $s\to b$, $a\to b$, $a\to t$ — are saturated, i.e. used to the limit).
• Conservation at $a$: in $= f(s,a) = 7$; out $= f(a,b)+f(a,t) = 4+3 = 7$. ✓
• Conservation at $b$: in $= f(a,b)+f(s,b) = 4+3 = 7$; out $= f(b,t) = 7$. ✓
• Value: out of $s$ is $f(s,a)+f(s,b) = 7+3 = 10$. Into $t$ is $f(a,t)+f(b,t) = 3+7 = 10$. They agree, as promised, and $\lvert f\rvert = 10$.

Let's confirm exactly this with code. The function below validates a flow against a capacity dictionary — a tool you'd genuinely want when debugging a flow algorithm.

def is_valid_flow(cap, flow, s, t):
    nodes = {u for e in cap for u in e}
    for e in cap:                                  # capacity constraint
        if not (0 <= flow.get(e, 0) <= cap[e]):
            return False
    for v in nodes - {s, t}:                       # conservation at internals
        inflow  = sum(flow.get((u, v), 0) for u in nodes)
        outflow = sum(flow.get((v, w), 0) for w in nodes)
        if inflow != outflow:
            return False
    return True

cap  = {("s","a"):10, ("s","b"):3, ("a","b"):4, ("a","t"):3, ("b","t"):10}
flow = {("s","a"):7,  ("s","b"):3, ("a","b"):4, ("a","t"):3, ("b","t"):7}
print(is_valid_flow(cap, flow, "s", "t"))
value = sum(flow[("s", w)] for w in "ab")
print("value =", value)
# Expected output:
# True
# value = 10

💡 Intuition: A flow network has two numbers on each edge once a flow is running: the capacity (fixed, the pipe's limit) and the flow (variable, how much you're currently sending). We usually write them as flow/capacity, e.g. 7/10. The whole game is to crank the flows up as high as the capacities and conservation allow.

🔄 Check Your Understanding 1. In network $M$, is the assignment $f(s,a)=10,\ f(a,b)=4,\ f(a,t)=3,\ f(s,b)=3,\ f(b,t)=7$ a valid flow? Check conservation at $a$. 2. Why must flow value measured at the source equal flow value measured at the sink? 3. An edge has capacity 5 and currently carries flow 5. What is this edge called, and what does it mean for the rest of the network?

Answers

1. No. At $a$: inflow $= f(s,a) = 10$, outflow $= f(a,b)+f(a,t) = 4+3 = 7$. Since $10 \neq 7$, conservation fails — 3 units would pile up at $a$. 2. By flow conservation, every internal vertex passes through exactly what it receives; summing the conservation equations, the only places net flow can enter or leave the whole network are $s$ and $t$, so out-of-$s$ = into-$t$. 3. It is saturated. A saturated edge is a candidate bottleneck: no more flow can use it unless flow elsewhere is rerouted to free up an alternative.

34.2 The max-flow problem

We now have flows; we want the best one.

Definition (maximum flow). The maximum-flow problem is: given a flow network $(G, c, s, t)$, find a flow $f$ of the greatest possible value $\lvert f\rvert$. Such an $f$ is a max flow (maximum flow).

Why is this hard enough to need a chapter? Because flow is a global property. You cannot just look at each edge in isolation and decide its flow; a choice you make on one edge constrains every downstream edge through conservation. A locally sensible decision can be globally wasteful.

Here is the trap, and it is worth feeling it before we fix it. The obvious greedy idea is: find any path from $s$ to $t$ with spare capacity, push as much as it allows, repeat until no such path exists. Let's see it fail on this clean network — call it $N$ — with four vertices $s, a, b, t$ and capacities

$$ c(s,a)=3,\quad c(s,b)=3,\quad c(a,t)=3,\quad c(b,t)=3,\quad c(a,b)=3. $$

The true maximum is clearly 6: send 3 along $s\to a\to t$ and 3 along $s\to b\to t$, using the two "outer" routes and ignoring the middle edge $a\to b$ entirely. Source out-capacity is $3+3=6$, so 6 is the most that could ever leave $s$; we can achieve it, so $\max = 6$.

But watch naive greed stumble. Suppose its first path is the "diagonal" $s\to a\to b\to t$:

• Push along $s\to a\to b\to t$: the bottleneck is $\min(3,3,3) = 3$. Now $s\to a$, $a\to b$, and $b\to t$ all carry 3. Flow so far $= 3$.
• Look for another augmenting path with spare capacity. $s\to b$ has room (3), but $b\to t$ is now full. $s\to a$ is full. $a\to t$ has room (3), but to reach $a$ from $s$ we'd need $s\to a$, which is full. There is no path of unused forward edges from $s$ to $t$.

Naive greed halts at value 3, but the true answer is 6. The first greedy choice committed flow to the middle edge $a\to b$ in a way that strands capacity on both sides. The fix — the single idea that makes max flow tractable — is to allow the algorithm to cancel a previous bad decision. That is what the next section builds.

🧩 Productive Struggle. Before reading §34.3, stare at network $N$ above with its 3-unit flow stuck on $s\to a\to b\to t$. We want to reroute: the 3 units sitting on $a\to b$ should instead go $a\to t$, freeing $b\to t$ for new flow from $s\to b$. What "move" would let an algorithm discover this rerouting automatically, using only local edge information? The answer is the residual back edge. See if you can invent it before we do.

🔄 Check Your Understanding 1. State the maximum-flow problem in one sentence. 2. Give a one-line argument that the max flow in network $N$ cannot exceed 6. 3. Why does naive "push on any spare path" greed fail, in terms of commitment?

Answers

1. Given a network with capacities, a source, and a sink, find a valid flow of the largest possible value. 2. Every unit of flow must leave $s$, and the edges out of $s$ have total capacity $3+3 = 6$; so $\lvert f\rvert \le 6$ for any flow. 3. It permanently commits flow to edges based on a local choice, with no mechanism to take it back; a single bad commitment (sending flow across $a\to b$) can block routes that a smarter allocation would have used.

34.3 Ford–Fulkerson and augmenting paths

The cure for premature commitment is to let the algorithm push flow backward to undo it. We capture both "remaining forward capacity" and "flow available to cancel" in a single structure: the residual network.

Definition (residual capacity, residual network). Given a flow $f$ on network $G$, the residual capacity of an ordered pair $(u,v)$ is $$c_f(u,v) \;=\; \underbrace{\big(c(u,v) - f(u,v)\big)}_{\text{spare forward capacity}} \;+\; \underbrace{f(v,u)}_{\text{flow on } v\to u \text{ we may cancel}}.$$ The residual network $G_f$ is the directed graph on the same vertices whose edges are exactly the pairs with $c_f(u,v) > 0$. It contains, for each original edge $u\to v$ carrying $f(u,v) < c(u,v)$, a forward edge with the spare capacity; and for each original edge $u\to v$ carrying $f(u,v) > 0$, a back edge $v\to u$ with capacity $f(u,v)$ (pushing flow on the back edge reduces the original flow).

The back edge is the whole trick. Sending one unit along a residual back edge $v\to u$ means "cancel one unit of the flow currently going $u\to v$" — exactly the undo that naive greed lacked.

Definition (augmenting path). An augmenting path is a directed path from $s$ to $t$ in the residual network $G_f$ (using forward and/or back edges, each with positive residual capacity). Its bottleneck is the minimum residual capacity along it. Pushing the bottleneck amount along the path produces a new valid flow whose value is larger by exactly the bottleneck.

Now the algorithm writes itself.

The Ford–Fulkerson method. 1. Start with the zero flow: $f(u,v) = 0$ on every edge. 2. While there is an augmenting path $p$ from $s$ to $t$ in the residual network $G_f$: - let $\Delta$ be the bottleneck (smallest residual capacity) on $p$; - for each step $u\to v$ on $p$: increase $f(u,v)$ by $\Delta$ if it is a forward edge, or decrease $f(v,u)$ by $\Delta$ if it is a back edge. 3. When no augmenting path remains, $f$ is a maximum flow.

We call it a method rather than a single algorithm because step 2 doesn't say how to find an augmenting path. Choose BFS (shortest augmenting path) and you get the Edmonds–Karp algorithm, which runs in $O(V E^2)$ time and is what we will implement; that is a Tier-1 refinement we cite but will not prove here.

Worked example: Ford–Fulkerson resolving the greedy trap

Let's run the method on the network $N$ where greed failed, so you can watch a back edge rescue the flow.

Recall $N$: $c(s,a)=c(s,b)=c(a,t)=c(b,t)=c(a,b)=3$.

The strategy first. We will deliberately pick the bad diagonal path first, to prove the method recovers anyway. The key moment is the second augmenting path: it will travel a back edge $b\to a$, which cancels flow on $a\to b$ and reroutes it. Watch the bottleneck arithmetic.

Iteration 1. Residual network = the original (zero flow, so every edge is at full residual capacity). Choose augmenting path $s\to a\to b\to t$. Bottleneck $= \min(3,3,3) = 3$. Push 3 forward on all three edges.

Flow now: $f(s,a)=3,\ f(a,b)=3,\ f(b,t)=3$, rest 0. Value $= 3$.

Residual changes: $s\to a$ now $c_f = 0$ forward but gains back edge $a\to s$ (cap 3); $a\to b$ now $c_f=0$ forward, back edge $b\to a$ (cap 3); $b\to t$ now $c_f=0$ forward, back edge $t\to b$ (cap 3).

Iteration 2. Find an augmenting path in the residual. Forward edges with room: $s\to b$ (3), $a\to t$ (3). Back edges available: $a\to s$, $b\to a$, $t\to b$. Can we get from $s$ to $t$? Try $s\to b$ (forward, residual 3), then we need to leave $b$: $b\to t$ is full forward, but $b\to a$ is an available back edge (residual 3) — take it. Now at $a$: $a\to t$ is forward with room (3). Path found: $$s \xrightarrow{\text{fwd}} b \xrightarrow{\text{back}} a \xrightarrow{\text{fwd}} t, \qquad \text{bottleneck} = \min(3,\,3,\,3) = 3.$$ Apply it: increase $f(s,b)$ by 3 (forward); the step $b\to a$ is a back edge, so decrease $f(a,b)$ by 3 (it goes $3 \to 0$); increase $f(a,t)$ by 3 (forward). Value $= 3 + 3 = 6$.

Flow now: $f(s,a)=3,\ f(s,b)=3,\ f(a,b)=0,\ f(a,t)=3,\ f(b,t)=3$.

Iteration 3. Residual: out of $s$, both $s\to a$ and $s\to b$ are saturated (carry 3 of 3) — no forward residual; the only residual edges out of $s$ would be back edges, but $s$ has no incoming flow to cancel. So no augmenting path exists. Stop. Max flow $= 6$. ✓

Notice what the back edge accomplished: the 3 units that were uselessly crossing $a\to b$ got rerouted to $a\to t$, and the freed capacity on $b\to t$ was filled by fresh flow from $s\to b$. The method discovered, with nothing but local residual capacities, the global rerouting that naive greed could never reach.

⚠️ Common Pitfall: When you push along a back edge $v\to u$, you must decrease $f(u,v)$ — never increase some imaginary edge $v\to u$. Students often add flow to a reverse edge that doesn't exist in the original network. The original edge set never changes; back edges live only in the residual graph and only subtract from existing flow.

Worked example: the primary network $M$

Now let's max-flow our main network $M$ ($c(s,a)=10, c(s,b)=3, c(a,b)=4, c(a,t)=3, c(b,t)=10$), choosing shortest augmenting paths (BFS / Edmonds–Karp), which is what the code does.

After iteration 3 the flow is exactly the one we validated in §34.1: $f(s,a)=7, f(s,b)=3, f(a,b)=4, f(a,t)=3, f(b,t)=7$, value $\mathbf{10}$. In iteration 4, BFS from $s$ can reach $a$ (the edge $s\to a$ still has residual $10-7=3$) but from $a$ every forward edge is saturated ($a\to b$ and $a\to t$ both full) and $b, t$ are unreachable — so no augmenting path, and the method stops. We will prove 10 is optimal in §34.4; for now, notice we have no path left to improve it.

Here is Ford–Fulkerson with BFS, from scratch (the Project Checkpoint turns this into the Toolkit's max_flow). Read it as the direct transcription of the method above:

from collections import deque

def max_flow_value(cap, s, t):
    res = {}                                    # residual capacities
    for (u, v), c in cap.items():
        res.setdefault(u, {}); res.setdefault(v, {})
        res[u][v] = res[u].get(v, 0) + c
        res[v].setdefault(u, 0)                 # reverse edge starts at 0
    total = 0
    while True:
        parent, q = {s: None}, deque([s])       # BFS for a shortest aug. path
        while q:
            u = q.popleft()
            for v, c in res[u].items():
                if c > 0 and v not in parent:
                    parent[v] = u; q.append(v)
        if t not in parent:                     # no augmenting path: done
            return total
        v, bottleneck = t, float("inf")         # find bottleneck along path
        while parent[v] is not None:
            bottleneck = min(bottleneck, res[parent[v]][v]); v = parent[v]
        v = t                                   # push flow / update residual
        while parent[v] is not None:
            res[parent[v]][v] -= bottleneck
            res[v][parent[v]] += bottleneck
            v = parent[v]
        total += bottleneck

cap = {("s","a"):10, ("s","b"):3, ("a","b"):4, ("a","t"):3, ("b","t"):10}
print(max_flow_value(cap, "s", "t"))
# Expected output:
# 10

🔄 Check Your Understanding 1. In the residual network, what does a back edge $v\to u$ with capacity 5 tell you about the current flow? 2. In iteration 2 of the $N$ example, which original edge had its flow decreased, and by how much? 3. Why is the zero flow always a valid starting point for Ford–Fulkerson?

Answers

1. It tells you the current flow sends exactly 5 units along the original edge $u\to v$ — pushing on the back edge would cancel up to 5 of them. 2. The edge $a\to b$ had its flow decreased by 3 (from 3 to 0), because the augmenting path used the back edge $b\to a$ with bottleneck 3. 3. The zero flow trivially satisfies both constraints — $0 \le c(u,v)$ for every edge (capacity), and $0 = 0$ at every vertex (conservation) — so it is a legal flow of value 0 to improve from.

34.4 The max-flow min-cut theorem

We have an algorithm that stops. But how do we know that when it stops, it has actually found the maximum — not just a flow it couldn't improve with its particular path choices? The answer is the jewel of this chapter, and it comes from a second, dual notion: a cut.

💡 Intuition: Forget pushing flow for a moment. Ask the opposite question: what is the cheapest way to disconnect $s$ from $t$? Pick a set of pipes to sever so that no water can get from source to sink, minimizing the total capacity you cut. Clearly any flow must "cross" any such barrier, so no flow can exceed the capacity of any barrier. The theorem says the best flow exactly matches the cheapest barrier — supply meets the binding constraint, with nothing wasted.

Definition (s–t cut). An s–t cut is a partition of the vertex set $V$ into two parts $(S, T)$ with $s \in S$ and $t \in T$ (so $T = V \setminus S$). The capacity of the cut is the total capacity of the edges going from $S$ to $T$: $$c(S, T) \;=\; \sum_{u \in S}\sum_{v \in T} c(u, v).$$ (Only edges crossing $S\to T$ count; edges that go $T\to S$ or stay within a side do not add to the cut capacity.) The min cut is an s–t cut of smallest capacity.

For network $M$, consider the partition $S = \{s, a\}$, $T = \{b, t\}$. The edges crossing from $S$ to $T$ are $s\to b$ (cap 3), $a\to b$ (cap 4), and $a\to t$ (cap 3). So $c(S,T) = 3 + 4 + 3 = 10$. Notice: that is exactly the max-flow value we found. That is not a coincidence — it is the theorem.

🚪 Threshold Concept. Max-flow min-cut is your first strong duality theorem: a maximization problem and a minimization problem whose optimal values are provably equal. This pattern — primal max equals dual min — is the beating heart of linear programming, game theory (von Neumann's minimax), and combinatorial optimization. Once you have seen one duality, you start looking for the dual of every optimization problem you meet, because the dual is often where the proof of optimality lives. Max-flow min-cut is the most visual instance you will ever see; let it teach you the shape of the idea.

First, the easy direction — it bounds every flow by every cut.

Lemma (weak duality). For any flow $f$ and any s–t cut $(S,T)$, $\ \lvert f\rvert \le c(S,T)$.

The strategy first. The value of a flow can be measured across any cut, not just at the source: the net flow crossing from $S$ to $T$ equals $\lvert f\rvert$. Once we know that, the bound is immediate — net crossing flow is at most the forward crossing flow, which is at most the forward crossing capacity, which is $c(S,T)$.

Proof. Summing the conservation equation over all $v \in S$ (and using that $s\in S$ contributes the value $\lvert f\rvert$, while every other vertex of $S$ contributes 0 net), the value equals the net flow crossing the cut: $$\lvert f\rvert \;=\; \underbrace{\sum_{u\in S}\sum_{v\in T} f(u,v)}_{\text{flow leaving } S} \;-\; \underbrace{\sum_{u\in S}\sum_{v\in T} f(v,u)}_{\text{flow returning to } S}.$$ The second sum is $\ge 0$, so $\lvert f\rvert \le \sum_{u\in S}\sum_{v\in T} f(u,v)$. By the capacity constraint $f(u,v)\le c(u,v)$ on each crossing edge, this is $\le \sum_{u\in S}\sum_{v\in T} c(u,v) = c(S,T)$. $\blacksquare$

Weak duality already gives a certificate: if you ever find a flow and a cut with equal value, you instantly know both are optimal — the flow can't be beaten (no flow exceeds that cut) and the cut can't be beaten (no cut falls below that flow). The deep half of the theorem says such a matching pair always exists.

The Max-Flow Min-Cut Theorem (Ford–Fulkerson; Elias–Feinstein–Shannon, 1956). In any flow network, the maximum value of a flow equals the minimum capacity of an s–t cut.

The strategy first. We prove the following are equivalent for a flow $f$: (i) $f$ is a max flow; (ii) the residual network $G_f$ has no augmenting path (no $s\to t$ residual path); (iii) $\lvert f\rvert = c(S,T)$ for some cut $(S,T)$. The cycle (i)$\Rightarrow$(ii)$\Rightarrow$(iii)$\Rightarrow$(i) closes the loop. The clever step is (ii)$\Rightarrow$(iii): when no augmenting path exists, the set of vertices still reachable from $s$ in the residual graph is the small side of a minimum cut. This is also exactly why Ford–Fulkerson is correct.

Proof.

(i) $\Rightarrow$ (ii). Contrapositive. If $G_f$ has an augmenting path, pushing its (positive) bottleneck yields a strictly larger flow, so $f$ was not maximum.

(ii) $\Rightarrow$ (iii). Suppose $G_f$ has no $s\to t$ path. Let $S$ be the set of vertices reachable from $s$ in the residual network $G_f$, and $T = V\setminus S$. Then $s\in S$, and $t\in T$ (else $t$ would be reachable, i.e. an augmenting path). Now examine any original edge crossing the cut: - For $u\in S,\ v\in T$ with edge $u\to v$: there is no residual edge $u\to v$ (or $v$ would be reachable, putting it in $S$). Residual capacity zero means $c(u,v) - f(u,v) = 0$, i.e. the edge is saturated: $f(u,v) = c(u,v)$. - For $u\in S,\ v\in T$ with a reverse original edge $v\to u$ carrying flow: that flow would create a residual back edge $u\to v$, again making $v$ reachable — contradiction. So every original edge from $T$ into $S$ carries zero flow: $f(v,u) = 0$.

Plug these into the cross-cut value formula from weak duality: the forward-crossing flow equals the full forward-crossing capacity, and the backward-crossing flow is 0. Hence $$\lvert f\rvert = \sum_{u\in S}\sum_{v\in T} f(u,v) - 0 = \sum_{u\in S}\sum_{v\in T} c(u,v) = c(S,T).$$

(iii) $\Rightarrow$ (i). If $\lvert f\rvert = c(S,T)$ for some cut, then by weak duality every flow $f'$ satisfies $\lvert f'\rvert \le c(S,T) = \lvert f\rvert$, so $f$ is maximum (and that cut is simultaneously minimum). $\blacksquare$

Three things fall out of this single proof, and you should hold all three:

1. A certificate of optimality. To prove a flow is maximum, exhibit a cut of equal capacity — found mechanically as "the residual-reachable set of $s$." No need to argue about every possible flow.
2. Ford–Fulkerson is correct. When the method halts, by definition no augmenting path remains — that is condition (ii) — so the flow it holds is maximum.
3. The min cut is the bottleneck. The saturated forward edges across the cut $(S,T)$ are exactly the binding constraints. Want more flow? You must widen one of those specific edges; widening anything else changes nothing.

Back to network $M$: when Edmonds–Karp halted, the residual-reachable set of $s$ was $S = \{s, a\}$ (recall iteration 4 reached $a$ but no further). The cut $(\{s,a\}, \{b,t\})$ has capacity $3+4+3 = 10$, matching the flow. So 10 is proved maximum — and if you wanted to ship more flow through $M$, point 3 tells you precisely which three edges to upgrade.

🐛 Find the Error. A teammate claims: "I found a flow of value 10 on network $M$ and a cut of capacity 12 (namely $S=\{s\}$, capacity $10+3 - $ wait, $s\to a$ is 10 and $s\to b$ is 3, so 13). Since my flow (10) is below my cut (13), my flow must not be maximum — there's a gap of 3 to close." Where is the reasoning wrong?

Answer

Weak duality says max-flow $\le$ every cut, so a flow being below some cut proves nothing about optimality — you can always find slack cuts (here the source cut $\{s\}$ has capacity $13 > 10$). Optimality is certified only by a cut whose capacity equals the flow, which is the minimum cut ($\{s,a\}\mid\{b,t\}$, capacity 10), not just any cut. The "gap" to the source cut is real but irrelevant; the binding cut is the internal one.

🔄 Check Your Understanding 1. State the max-flow min-cut theorem in one sentence. 2. Given a max flow, how do you construct a minimum cut from it? 3. True or false: every edge crossing a minimum cut from $S$ to $T$ is saturated. Justify.

Answers

1. In any flow network, the maximum flow value equals the minimum s–t cut capacity. 2. Run Ford–Fulkerson to a max flow $f$; let $S$ be the vertices reachable from $s$ in the residual network $G_f$ and $T$ the rest. $(S,T)$ is a minimum cut. 3. True: in the proof of (ii)$\Rightarrow$(iii), every $S\to T$ edge had zero residual capacity, i.e. $f(u,v) = c(u,v)$ (saturated); that equality is exactly what makes the flow value equal the cut capacity.

34.5 Bipartite matching

Now the payoff that connects back to the social-network thread. We have a powerful, proven hammer (max flow). Let's find a problem that doesn't look like a nail and turn it into one.

A dating app, a job-assignment system, and a course-scheduling tool all face the same question: given two groups and a set of compatible pairs between them, how many disjoint pairings can we make at once? Concretely: three workers $\{1,2,3\}$ and three tasks $\{x,y,z\}$, where worker $i$ can do task $j$ only if they're connected. We want the largest set of (worker, task) assignments such that no worker does two tasks and no task is done by two workers.

This is a graph problem, and the graph is bipartite — vertices split into two sides with edges only crossing between them.

🔗 Connection. You met bipartite graphs in Chapter 27: a graph whose vertices split into two parts $X, Y$ with every edge crossing between the parts (equivalently, no odd cycle). Here the two parts are the two groups to be matched. We use that definition; we do not redefine it.

Definition (matching, maximum matching). A matching in a graph is a set $M \subseteq E$ of edges, no two of which share a vertex (every vertex is incident to at most one edge of $M$). A vertex incident to an edge of $M$ is matched; otherwise it is unmatched (or exposed). A maximum matching is a matching with the greatest number of edges. A bipartite matching is a matching in a bipartite graph. A matching that covers every vertex on a side is a perfect matching of that side.

Our worker–task example: edges $1{-}x,\ 1{-}y,\ 2{-}x,\ 3{-}y,\ 3{-}z$. By inspection, $\{1{-}y,\ 2{-}x,\ 3{-}z\}$ is a matching of size 3 — every worker and every task is used, so it's perfect and certainly maximum (you can't exceed $\min(3,3)=3$). But "by inspection" doesn't scale, and it doesn't generalize to thousands of pairs. We want an algorithm. We already have one.

The reduction (bipartite matching $\to$ max flow). Given a bipartite graph with parts $X$ and $Y$ and edge set $E$, build a flow network: 1. Add a source $s$ and a sink $t$. 2. Add an edge $s \to x$ of capacity 1 for every $x \in X$. 3. Direct every original edge $x{-}y$ as $x \to y$ with capacity 1. 4. Add an edge $y \to t$ of capacity 1 for every $y \in Y$.

Then the value of a maximum integer flow equals the size of a maximum matching, and the matching is exactly the set of middle edges $x\to y$ that carry one unit of flow.

The strategy first. Two directions. (Matching $\Rightarrow$ flow): a matching of size $k$ gives $k$ vertex-disjoint paths $s\to x\to y\to t$, hence an integer flow of value $k$. (Flow $\Rightarrow$ matching): the capacity-1 edges $s\to x$ and $y\to t$ force each $x$ to send at most one unit and each $y$ to receive at most one unit, so the saturated middle edges form a matching of size $\lvert f\rvert$. The only subtlety is that we need an integer flow; Ford–Fulkerson started from the zero flow always produces integer flows when all capacities are integers, because every bottleneck is an integer.

Why it works. Consider any integer flow $f$. Each $x\in X$ has a single incoming edge $s\to x$ of capacity 1, so by conservation $x$ sends out at most 1 unit total — at most one middle edge $x\to y$ carries flow. Symmetrically each $y\in Y$ has a single outgoing edge $y\to t$ of capacity 1, so receives at most 1 unit — at most one middle edge into $y$ carries flow. Thus the set $M = \{\,x{-}y : f(x,y) = 1\,\}$ has no two edges sharing an $x$ or a $y$: it is a matching, of size $\lvert f\rvert$. Conversely a matching of size $k$ yields the obvious flow of value $k$. So the maximum of one equals the maximum of the other. $\blacksquare$

Let's apply it to the worker–task example. The flow network has unit-capacity edges $s\to 1, s\to 2, s\to 3$; the middle edges $1\to x, 1\to y, 2\to x, 3\to y, 3\to z$; and $x\to t, y\to t, z\to t$. Running Ford–Fulkerson finds three vertex-disjoint augmenting paths — for instance $s\to 1\to y\to t$, then $s\to 2\to x\to t$, then $s\to 3\to z\to t$ — for a max flow of value 3. The middle edges carrying flow are $1{-}y,\ 2{-}x,\ 3{-}z$: exactly a maximum matching of size 3.

Here is the reduction in code, reusing the max_flow_value of §34.3:

def max_bipartite_matching(left, edges):
    cap = {}
    for x in left:                              # source -> each left vertex
        cap[("s", ("L", x))] = 1
    seen_right = set()
    for x, y in edges:                          # left -> right (the middle)
        cap[(("L", x), ("R", y))] = 1
        seen_right.add(y)
    for y in seen_right:                        # each right vertex -> sink
        cap[(("R", y), "t")] = 1
    return max_flow_value(cap, "s", "t")        # value == matching size

workers = [1, 2, 3]
compat  = [(1,"x"), (1,"y"), (2,"x"), (3,"y"), (3,"z")]
print(max_bipartite_matching(workers, compat))
# Expected output:
# 3

When can't we match everyone? The answer is one of the prettiest theorems in combinatorics, and max-flow min-cut proves it almost for free.

Hall's Marriage Theorem. A bipartite graph with parts $X, Y$ has a matching that saturates $X$ (matches every vertex of $X$) if and only if for every subset $W \subseteq X$, the neighborhood $N(W)$ satisfies $\lvert N(W)\rvert \ge \lvert W\rvert$.

In words: a group of workers can all be assigned distinct tasks iff every sub-group of workers, taken together, is collectively compatible with at least as many tasks as there are workers in the sub-group. The "only if" is obvious (you can't match $k$ workers into fewer than $k$ tasks). The "if" is the content, and it follows from max-flow min-cut: if no $X$-saturating matching exists, the max flow is $< \lvert X\rvert$, so the min cut is $< \lvert X\rvert$, and unpacking which edges that cut contains produces exactly a set $W$ with $\lvert N(W)\rvert < \lvert W\rvert$. (The full unpacking is a guided exercise.)

💡 Intuition: Hall's condition is a deficiency test. The single worst-offending sub-group — the one with the biggest shortfall $\lvert W\rvert - \lvert N(W)\rvert$ — is the bottleneck, and it corresponds to the min cut. For example, if workers 2 and 3 are both only qualified for task $x$, then $W = \{2,3\}$ has $N(W) = \{x\}$, $\lvert N(W)\rvert = 1 < 2$, and no full assignment exists — you can match at most one of them.

🔄 Check Your Understanding 1. In the flow reduction, why does every $s\to x$ and $y\to t$ edge get capacity exactly 1? 2. A maximum flow on the reduced network has value 4. What is the size of the maximum matching? 3. Bipartite graph: $X=\{1,2,3\}$, $Y=\{x,y\}$, edges $1{-}x, 2{-}x, 3{-}x, 1{-}y$. Is there a matching saturating $X$? Use Hall's condition.

Answers

1. Capacity 1 enforces that each left vertex is used by at most one assignment and each right vertex is taken by at most one assignment — the defining no-shared-vertex property of a matching. 2. The maximum matching has size 4 (matching size = max-flow value). 3. No. Take $W = \{2,3\}$: $N(W) = \{x\}$, so $\lvert N(W)\rvert = 1 < 2 = \lvert W\rvert$. Hall's condition fails for $W$, so no matching can saturate $X$ (workers 2 and 3 compete for the only task they can do; the max matching has size 2, e.g. $1{-}y, 2{-}x$).

34.6 Applications: assignment, scheduling, and segmentation

Flow and matching are modeling languages. The skill is recognizing their shape inside a messy problem, then letting the algorithm do the work. A quick tour of three classics.

Assignment (the obvious one). Any "assign agents to jobs respecting compatibility, maximize the number assigned" problem is bipartite matching: agents on the left, jobs on the right, an edge for each qualification. Add capacities $> 1$ on the source/sink edges and you model capacitated assignment — e.g., a server that can handle 3 jobs becomes a left vertex with an incoming edge of capacity 3. This single generalization covers staff scheduling, room booking, and load balancing.

Scheduling with conflicts. Suppose tasks must be assigned to time slots, each slot holding a limited number of tasks, with eligibility constraints (a task can only run in certain slots). Tasks on the left, slots on the right, edge = eligibility, slot-to-sink capacity = slot size. A max flow that saturates the source means all tasks scheduled; if it doesn't, the min cut tells you which group of tasks is over-subscribed for its eligible slots — actionable diagnostic information, not just a "no."

Image segmentation (the surprising one). To separate a foreground object from the background, model each pixel as a vertex; connect the source to pixels that look like foreground and pixels that look like background to the sink, with capacities reflecting confidence; connect neighboring pixels with capacities reflecting how much we'd "pay" to put a boundary between them. A minimum cut then partitions the pixels into foreground ($S$) and background ($T$) while paying the least total penalty — exactly a balance of per-pixel evidence against boundary smoothness. The min cut is the segmentation. This "graph cut" technique was a workhorse of computer vision for years, and it is nothing but the dual side of the very theorem you proved in §34.4.

🔗 Connection. Image segmentation uses min cut, while assignment uses max flow — but by the max-flow min-cut theorem these are the same computation. Run one algorithm; read off either answer. That two superficially unrelated applications (routing capacity vs. drawing object boundaries) are solved by one theorem is the recurring lesson of this book: the right abstraction unifies problems that look nothing alike (theme three).

🔄 Check Your Understanding 1. Your job-assignment max flow does not saturate the source. What does the min cut tell you, and why is that more useful than "infeasible"? 2. In image segmentation, which side of the min cut is the foreground, and what does a high capacity between two neighboring pixels encode?

Answers

1. The min cut identifies a specific set $W$ of tasks/agents whose eligible capacity is exhausted (the bottleneck) — by Hall's-style reasoning, a sub-group with $\lvert N(W)\rvert < \lvert W\rvert$. That points you to exactly which constraint to relax (add a slot, broaden eligibility), instead of just reporting failure. 2. The source side $S$ is the foreground (those pixels stayed connected to $s$). A high capacity between neighbors encodes a strong preference not to cut between them — i.e., they likely belong to the same region, so a boundary there is expensive.

Project Checkpoint: max_flow for the Toolkit

This is the capstone of the graphs.py module. You began the Graph class in Chapter 27, added bfs/dfs in Chapter 28, dijkstra in Chapter 29, and mst_kruskal in Chapter 32. Now you add the most powerful function of all — max_flow(g, s, t) — which subsumes a whole family of allocation problems and, via the reduction in §34.5, solves bipartite matching too.

We implement the Edmonds–Karp form of Ford–Fulkerson: repeatedly find a shortest augmenting path with BFS, push its bottleneck, and stop when the sink becomes unreachable in the residual network. The signature is the canonical one from the frozen Toolkit API: max_flow(g, s, t) returning the maximum flow value. We keep the same Graph stub used in Chapter 29 (an adjacency dict of (neighbor, capacity) pairs) so the piece composes with the rest of the package.

from collections import deque

def max_flow(g, s, t):
    """Max flow value from s to t (Edmonds-Karp: BFS-chosen augmenting paths).
    g.neighbors(u) yields (v, capacity); g.vertices() yields all vertices."""
    res = {u: {} for u in g.vertices()}              # residual capacities
    for u in g.vertices():
        for v, c in g.neighbors(u):
            res[u][v] = res[u].get(v, 0) + c
            res.setdefault(v, {}).setdefault(u, 0)   # reverse edge starts at 0
    total = 0
    while True:
        parent, q = {s: None}, deque([s])            # BFS for a shortest path
        while q:
            u = q.popleft()
            for v, c in res[u].items():
                if c > 0 and v not in parent:
                    parent[v] = u; q.append(v)
        if t not in parent:                          # no augmenting path: done
            return total
        v, bottleneck = t, float("inf")              # bottleneck along the path
        while parent[v] is not None:
            bottleneck = min(bottleneck, res[parent[v]][v]); v = parent[v]
        v = t
        while parent[v] is not None:                 # update residual capacities
            res[parent[v]][v] -= bottleneck
            res[v][parent[v]] += bottleneck
            v = parent[v]
        total += bottleneck

On our primary network $M$ this returns 10, matching the hand-trace table in §34.3 and the min cut we proved in §34.4. Because every capacity is an integer and Ford–Fulkerson starts from the zero flow, every bottleneck is an integer, so the result is always integral — which is exactly what makes the bipartite-matching reduction work: feed max_flow the reduced unit-capacity network from §34.5 and its return value is the maximum matching size.

Toward the capstone. max_flow completes the algorithmic core of graphs.py. In Chapter 39's Track B (the social-network analyzer), you will use it to answer questions pure traversal cannot — the maximum number of edge-disjoint paths between two people (network resilience), or the largest set of compatible pairings in a recommendation graph. With bfs, dijkstra, mst_kruskal, and now max_flow, your Toolkit can model connectivity, distance, design, and allocation — the four questions almost every graph problem in practice reduces to.

Toolkit so far: logic.py, sets.py, relations.py, combinatorics.py, recurrences.py, probability.py, numbertheory.py, crypto.py, coding.py, and a now nearly complete graphs.py (Graph, bfs, dfs, dijkstra, mst_kruskal, max_flow).

Summary

Network flow models "how much can I push from $s$ to $t$ respecting capacities," and a remarkable theorem ties it to its dual, the cheapest cut. The reference facts:

Core objects

Key results

Algorithm (Ford–Fulkerson / Edmonds–Karp). Start at zero flow; while an augmenting path exists in $G_f$, push its bottleneck (forward edges add, back edges subtract existing flow); stop when $t$ is unreachable. BFS path choice gives Edmonds–Karp, $O(VE^2)$.

When to use what

Common pitfalls

• A back edge $v\to u$ subtracts from $f(u,v)$; it is not a new original edge.
• A flow below some cut proves nothing — only a cut of equal capacity certifies optimality.
• Only $S\to T$ edges count toward cut capacity; $T\to S$ edges and within-side edges do not.
• Bipartite matching needs the integer max flow; non-integer flows do not correspond to matchings.

Spaced Review

Retrieval strengthens memory. Answer from memory before expanding the solution.

1. (Ch. 32) Both Kruskal's MST algorithm and Ford–Fulkerson are greedy-with-a-correctness-theorem. State the property that certifies Kruskal's choices are safe, and name the analogous certificate for max flow.
2. (Ch. 32) A minimum spanning tree minimizes total edge weight subject to connecting all vertices. A minimum cut minimizes total capacity subject to disconnecting $s$ from $t$. In one sentence, why is "minimum cut" a maximization problem in disguise?
3. (Ch. 29) Dijkstra and the BFS inside Edmonds–Karp both explore a graph from a source, but they answer different questions and require different conditions. What does each compute, and what does Dijkstra require of edge weights that BFS does not?
4. (Ch. 29) In Chapter 29 an edge weight meant a cost along one path; in this chapter it means a capacity for an aggregate flow. Give one concrete real-world quantity that is naturally a cost, and one that is naturally a capacity.

Answers

1. Kruskal is certified by the cut property (the lightest edge crossing any cut is safe to include in some MST). Max flow is certified by the max-flow min-cut theorem — exhibiting an s–t cut whose capacity equals the flow value proves the flow is maximum. 2. By max-flow min-cut, the minimum cut capacity equals the maximum flow value; minimizing the cut is solving the maximization (max flow) by its dual. 3. BFS computes a shortest path by number of edges (and finds shortest augmenting paths for Edmonds–Karp); Dijkstra computes shortest paths by total weight. Dijkstra requires non-negative edge weights; plain BFS does not use weights at all (it treats every edge as length 1). 4. Cost: travel time or distance on a road (you minimize it along your route). Capacity: the bandwidth of a network link or the throughput of a pipe (it caps an aggregate, not a single trip). (Other reasonable answers accepted.)

What's Next

You have now built the full graph-algorithms toolkit — traversal, shortest paths, spanning trees, coloring, and flow — and you have met your first strong duality theorem, where a maximum and a minimum provably coincide. That pattern, and the modeling instinct to reduce one problem to another you already know how to solve, are exactly the habits Part VI demands. There, the questions turn from "how do I compute this efficiently?" to the deeper "can this be computed at all, and if so, can it be computed efficiently?" We leave Part V's concrete algorithms for the theory of computation: finite automata and the languages they recognize (Chapter 35), the problems no program can ever solve (Chapter 36), and the great open question — $P$ versus $NP$ — about the problems we suspect no program can solve quickly (Chapter 37). The flow and matching reductions you just learned are a first taste of the reduction technique that will become the central tool for classifying problems by difficulty. Onward.