A Bit of History
Network flow theory has an unusually dramatic origin: in 1955, RAND Corporation researchers T. E. Harris and F. S. Ross produced a classified report analyzing the capacity of the Soviet Union's railway network connecting it to Eastern Europe — explicitly framed, in Cold War terms, around how much material could flow through the network and which links, if disrupted, would bottleneck it most severely (a real map from that report, showing a specific rail "bottleneck," was declassified decades later). The following year, L. R. Ford Jr. (the same Ford of Bellman-Ford, from an earlier deep dive) and D. R. Fulkerson formalized the underlying mathematics in their 1956 RAND report "Maximal Flow Through a Network," proving the max-flow min-cut theorem and giving the world its first general algorithm for computing it — directly inspired by a literal Cold War logistics problem.
Flow Network Fundamentals
A flow network is a directed graph with a designated source \(s\) and sink \(t\). Every directed edge \((u,v)\) has a non-negative capacity \(c(u,v)\): the most that edge is allowed to carry. A flow \(f(u,v)\) is the amount we actually choose to send. The distinction is worth keeping explicit: capacity is a ceiling; flow is current usage.
Flow is constrained locally, but measured globally
On an edge labeled 3 / 5, three units are currently flowing through a pipe that could carry at most five. At an ordinary junction, whatever enters must leave. Only the source is allowed to create net outgoing flow, and only the sink is allowed to absorb it.
The two rules a legal flow must obey
The first line is the capacity constraint. The second is flow conservation. Conservation is easiest to remember as a bookkeeping law: intermediate vertices may split or merge flow, but they cannot manufacture or destroy it. This is why the total amount leaving \(s\) must equal the total amount entering \(t\).
Analogy: Water Through Pipes
Picture capacities as pipe diameters and flow as the water currently moving through them. A junction may divide five units into three units on one outgoing pipe and two on another, but it cannot send six unless an extra unit came in. The maximum-flow problem asks for the largest sustainable source-to-sink throughput, not the largest value on any single edge.
Memory Hook: Capacity is permission; flow is commitment
An unused capacity of two units does not mean two units must be sent. It only means the algorithm still has room to send up to two more if doing so helps the global source-to-sink objective.
Residual Networks & Augmenting Paths
The residual network is the idea that makes max-flow algorithms much more than “keep sending greedily until stuck.” Given a current flow \(f\), it records what changes are still legal. For an original edge \(u\to v\), there are two possible moves: push more flow forward, or cancel some of the flow that was previously sent.
A residual graph is an “edit history” for the current flow
Suppose an edge has capacity 5 and currently carries 3. You may still push 2 more units forward. Just as importantly, the residual graph creates a reverse option of capacity 3, meaning up to three previously committed units can be withdrawn and rerouted elsewhere.
Augmenting paths: improve the whole flow by the bottleneck
An augmenting path is any \(s\)-to-\(t\) path in the residual network with positive residual capacity on every edge. You cannot push an arbitrary amount along it: the smallest residual capacity on the path is the bottleneck. That minimum tells you exactly how much the total flow can safely increase in one augmentation.
The narrowest residual edge controls the entire path
After the augmentation, each forward residual capacity on this path falls by 2 and each corresponding reverse residual capacity rises by 2. The residual graph therefore remembers both the progress we made and exactly how much of that choice could later be undone.
Ford–Fulkerson in one sentence
While an augmenting path exists, push its bottleneck amount; stop only when no residual path from \(s\) to \(t\) remains. Different algorithms mainly differ in how they choose the next augmenting path. Edmonds–Karp, for example, always chooses a shortest one in number of edges using BFS.
The Max-Flow Min-Cut Theorem
An \(s\)-\(t\) cut partitions the vertices into two sets \((S,T)\), with \(s\in S\) and \(t\in T\). Its capacity counts only original edges directed from \(S\) to \(T\):
The theorem says the best possible transportation plan and the narrowest possible bottleneck boundary have exactly the same numerical value. This is a duality: one side asks “how much can I send?”, the other asks “what is the cheapest boundary that every unit must cross?”
A cut is an upper bound; equality is a certificate
When flow value = cut capacity, both sides are optimal
Why every cut is an upper bound. By flow conservation, the net flow leaving the \(S\)-side of any cut equals the overall flow value \(|f|\). The forward edges crossing from \(S\) to \(T\) can carry at most their capacities, so \(|f|\le c(S,T)\) for every cut. Therefore no flow can ever beat the minimum cut.
Why Ford–Fulkerson eventually reaches equality. When no augmenting path remains, let \(S\) be exactly the vertices still reachable from \(s\) in the residual graph and let \(T=V\setminus S\). Then every original edge from \(S\) to \(T\) must be saturated—otherwise it would have positive forward residual capacity and its endpoint would also be reachable. Likewise, any original edge from \(T\) back to \(S\) carries zero net contribution across the boundary at optimality. The current flow therefore matches the capacity of this cut, giving the equality the theorem promises.
The optimization certificate
A candidate flow by itself says “I managed to send this much.” A cut by itself says “nobody can ever send more than this.” When the two numbers match, there is no gap left to argue about. This is why max-flow/min-cut is especially satisfying algorithmically: the solution comes with a compact proof that it is optimal.
Flow Reductions
The deeper lesson of network flow is that the “substance” moving through the network does not have to be water, trains, or data. A unit of flow can represent a matched pair, a selected path, a scheduled job, or a yes/no decision. The art is to build capacities so that legal flows correspond exactly to legal solutions of the original problem.
Why unit capacities turn flow into discrete choices
Integrality Theorem
If every capacity is an integer, there exists a maximum flow in which every edge flow is an integer. Ford–Fulkerson preserves this automatically when it augments by integer bottlenecks. This is the bridge from a seemingly continuous “amount of stuff” problem to discrete combinatorial objects like matchings: with capacity 1, an edge ends up carrying either 0 or 1 unit.
A matching is just a unit-capacity flow network in disguise
Connect a super-source to every left-side vertex with capacity 1, every allowed left-to-right pair with capacity 1, and every right-side vertex to a super-sink with capacity 1. Conservation plus unit capacities ensures no person can be used twice. Every unit of source-to-sink flow therefore selects one disjoint matched pair.
The same pattern extends further. Edge-disjoint paths use capacity 1 on original edges: each unit of integral flow becomes one path that cannot share an edge with another. For vertex-disjoint paths, split each vertex \(v\) into \(v_{in}\to v_{out}\) with capacity 1, forcing at most one unit of flow through that vertex. This is the algorithmic face of Menger's theorem from Part 8.
Ask three questions when turning a problem into flow
A matched pair? A path? A selected job? Decide what a single unit of flow represents.
Use capacities to encode exclusivity, quotas, resource limits, or “at most one.”
Use intermediate vertices to force units entering a choice or resource to leave consistently.
Other classic reductions include project selection (profits and prerequisite dependencies become an \(s\)-\(t\) min-cut), assignment and scheduling variants, and the whimsically named baseball elimination problem. They look unrelated on the surface; the common structure is that a cut or an integral flow encodes the combinatorial decision.
Real-World Applications
Airline Scheduling and Image Segmentation
Airlines model crew and aircraft scheduling constraints as flow networks to find feasible assignments respecting capacity limits (aircraft availability, crew rest requirements). In computer vision, min-cut image segmentation treats each pixel as a vertex, models "how likely two adjacent pixels belong to the same region" as edge capacity, and finds a minimum cut separating foreground from background — the max-flow min-cut theorem turning a continuous-looking visual problem into an exactly solvable discrete one.
One theorem, two interpretations
In logistics, a minimum cut identifies the infrastructure whose combined capacity forms the true bottleneck. In image segmentation, a minimum cut identifies the cheapest boundary separating foreground from background. The mathematics is identical; only the meaning assigned to capacities changes.
Exercises
- Construct a small flow network (4-5 vertices) and find its maximum flow by hand, then identify the corresponding minimum cut and verify their values match.
- Explain why reverse residual edges are necessary for correctness — construct a small example where a greedy augmenting-path choice without them gets stuck below the true maximum flow.
- Model the "can vertex-disjoint paths still connect \(s\) and \(t\) after removing \(k\) vertices" question (Part 8's Menger's theorem) as a flow problem with vertex capacities of 1.
- Challenge: Formulate the baseball elimination problem as a flow network for a small 4-team scenario (with remaining games between specific pairs), and determine using max-flow whether a given team is mathematically eliminated.
Conclusion & Next Steps
The max-flow min-cut theorem is one of the most quietly powerful results in this entire series — it directly generalizes Menger's theorem, and reduces bipartite matching, disjoint paths, and scheduling problems that don't superficially resemble flow at all. Next, we specialize this machinery to one of its most important applications: matching vertices optimally in bipartite graphs.
Next in the Series
In Part 16: Matching Theory, we meet Hall's Marriage Theorem, König's theorem, and the flow-based and combinatorial algorithms that compute optimal matchings.