The bottleneck is the whole story

A network of roads, each with a number on it saying how much can pass along it per hour, and two places marked $s$ and $t$. How much can get from $s$ to $t$ at once?

There is an obvious upper bound and it is worth taking seriously. Draw a line separating $s$ from $t$; everything travelling between them has to cross that line, so the total capacity of the roads crossing it is a ceiling. Different lines give different ceilings, and the best ceiling is the smallest of them.

The theorem is that the smallest ceiling is achieved. Not approached, not approximately met — achieved exactly, in whole numbers when the capacities are whole numbers.

What a flow is, and what a cut is #

A flow assigns to each road a number no bigger than its capacity, such that every place other than $s$ and $t$ passes on exactly what it receives. Its value is the net amount leaving $s$, which conservation forces to equal the net amount arriving at $t$ — a fact that is checked in every figure here rather than assumed, because it is the first thing an implementation gets wrong.

A cut is a set of places containing $s$ and not $t$. Its capacity is the total capacity of the roads leading out of that set — and only out. Roads leading back in are free, which is the part most easily got wrong and the part that makes the theorem true rather than merely plausible.

That asymmetry has a reason. A road running backwards into the cut cannot help anything cross it; traffic on such a road has to leave the set again somewhere else, and that second crossing is already counted. Counting it in both directions would make cuts look more expensive than they are, and the minimum would come out too high.

Why the easy half is easy #

Every flow is at most every cut. That is one line: the flow’s value is the net amount crossing the cut, which is what leaves the set minus what re-enters it, and that is at most what leaves, which is at most the total capacity of the roads leaving.

So $\max \text{flow} \le \min \text{cut}$, and it is worth pausing on how weak that statement is on its own. It says a maximum is at most a minimum, which is true of any two families related this way and carries no information about whether the gap is zero. Two numbers that have to meet makes the same easy observation for linear programs and then does the same hard work to close the gap; the pattern is the same and so is the proportion of the difficulty.

Why the hard half is true #

Take a flow that cannot be increased along any route with room left. Define a set $S$: put $s$ in it, and add every place reachable from $s$ by a sequence of steps, where a step goes forward along a road not yet full, or backwards along a road carrying something.

$t$ is not in $S$ — if it were, the sequence of steps would be a way of pushing more through, and the flow would not have been maximal. So $S$ is a cut.

Now look at the roads leaving $S$. Each of them must be full: if one had room, its far end would have been reachable and would be in $S$. And each road entering $S$ must be empty: if one carried anything, its near end would have been reachable backwards. So the flow’s value — what leaves $S$ minus what enters it — is exactly the total capacity leaving $S$ minus zero, which is the cut’s capacity.

A flow and a cut with the same number. The flow cannot exceed any cut and this cut cannot exceed this flow, so both are optimal, and both proofs are the same sentence read in opposite directions.

The certificate is the point #

There is a habit worth extracting from this, and it is not really about networks.

Establishing that a number is the maximum of something usually requires two entirely different arguments: an example achieving it, and a reason nothing does better. The example is often easy to find and always easy to check. The reason is the hard part, and it is generally an argument rather than an object — which means it cannot be handed to somebody else and verified in a minute.

The cut is a reason in the form of an object. Hand somebody a flow of value 5 and a cut of capacity 5, and they can check both facts by arithmetic on the drawing without knowing how either was found, and having checked, they know 5 is optimal. The theorem converts a proof into a certificate, and that conversion is what makes the min-max form worth having beyond the number it produces.

The figures here use it in exactly that way. How the flow is found is a method and is not the subject; nothing in this essay counts a step or asks how long anything takes. What is checked is that the flow is feasible, that the cut is a cut, and that the two numbers agree — and separately, by enumerating every cut, that no smaller one exists.

The same theorem, counting routes #

Give every road capacity one. A flow of value $k$ is then $k$ routes from $s$ to $t$ no two of which use the same road, and a cut of capacity $k$ is $k$ roads whose removal disconnects $s$ from $t$.

The theorem becomes: the most routes that share no road equals the fewest roads whose removal separates the ends. That is Menger’s theorem, published in 1927, thirty years before flows were thought about at all.

Menger’s theorem in this form is a statement about connectivity, and it has a vertex version — the most routes sharing no intermediate place equals the fewest places whose removal disconnects — which is the one used to define how robustly a network holds together.

The two versions are not the same theorem, but each follows from the other by a construction that splits each place into an in-copy and an out-copy joined by a single road of capacity one. That trick converts vertex constraints into edge constraints, which is the standard way of getting a theorem about places out of a theorem about roads.

Hall’s theorem is this theorem #

One bottleneck and nothing else says that a bipartite graph has a matching covering one side exactly when no subset of that side has fewer neighbours than members. That is a min-max statement too, and it is the flow theorem in disguise.

Build a network: a source joined to every point on the left with capacity one, every original edge with capacity one, every point on the right joined to a sink with capacity one. A flow of value $k$ is a matching of size $k$, because the capacities force each left point to send at most one unit and each right point to receive at most one.

A cut then corresponds to a choice of which left points to abandon and which right points to buy, and minimising its capacity is exactly minimising $|A| - |N(A)|$ over subsets $A$ of the left. The min-max theorem says the matching size equals that minimum, which rearranges into Hall’s condition.

This is not a curiosity. König’s theorem on bipartite graphs, Dilworth’s theorem on partially ordered sets, Menger’s theorem and Hall’s are all instances of the same min-max result, and the standard way of proving any of them today is to build the network and quote the flow theorem. Recognising a problem as a flow problem is most of the work of solving it.

What the theorem needs, and what it does not #

Whole numbers are not required, but they are rewarded. The theorem holds for real capacities. What is special about integer capacities is that a maximum flow with integer values on every road then exists — the integrality theorem — which is why the matching application works at all. A matching is a flow that must be zero or one on each edge, and without integrality the flow theorem would produce halves.

Direction matters and undirected networks are fine anyway. An undirected road of capacity $c$ is modelled by two directed roads of capacity $c$ in opposite directions, and the theorem applies unchanged.

Multiple sources are fine. Add a super-source joined to each of them with unlimited capacity. The same for multiple sinks. Nothing about the theorem is disturbed, which is a sign it is about the right thing.

More than one commodity is not fine. If two different kinds of traffic have to travel between two different pairs of places on the same network, the min-max equality fails — there are networks where every cut has capacity 2 and the most that can be routed is $3/2$. That failure is not a technicality; it is the boundary of the subject, and multi-commodity flow is a genuinely harder object with no clean certificate.

When the numbers are not whole #

Every capacity in the figures here is a whole number, and that is not decoration.

For real-valued capacities the theorem still holds — the same proof works, with the reachable set defined by “not full” and “not empty” as before. What changes is that the search for an improving route can go on for ever. There is a famous network of Ford and Fulkerson’s own devising, with capacities involving the golden ratio, on which routes with room left keep being found and the flow’s value converges to a quarter of the true maximum. The theorem is not damaged by this; the theorem is about the existence of the equality, and it is the finding that fails.

With whole-number capacities that cannot happen. Every improving push adds at least one to the value, and the value is bounded, so the process stops. And it stops at a flow whose value on every road is a whole number, which is the integrality theorem and the reason every application in this essay works.

That last point is worth separating from the rest, because it is the one people forget. The flow theorem does not merely say a maximum flow exists; it says that when the capacities are whole numbers, a maximum flow with whole-number values exists. A matching is a flow forced to be 0 or 1 on every edge, and without integrality the theorem would hand back a “matching” using half of one edge and half of another — a perfectly good flow and not a matching at all. Every combinatorial consequence of the theorem rests on that clause.

That last figure is the honest advertisement for the theorem. On a network of four places the answer can be seen; on a network of seven it cannot, and the cut that certifies the answer is not the set of roads out of the source, or into the sink, or any of the places a guess would land. The theorem is not needed to believe the answer — the flow is right there — but it is needed to know that no answer is better, and the certificate it produces is the only short reason available.

Where it came from #

Ford and Fulkerson proved the theorem in 1956, working at RAND on a question about rail capacity. Menger’s theorem had been available since 1927 and the connection was not immediately noticed; Elias, Feinstein and Shannon published the same result independently in the same year, coming at it from information theory.

The problem that motivated it was, characteristically for the period, a question about how much could be moved along a rail network and where it would be most effective to interrupt it. The cut side of the theorem was the side of interest.

What survived the motivation is the min-max form. The 1950s produced several theorems of exactly this shape — linear programming duality, the minimax theorem for zero-sum games, this one — and the recognition that they are versions of one another came slowly and is now the standard organising view. The value from both sides is the game-theoretic member of that family.

What the pictures cannot show #

Every network drawn here has at most eight places, because the cut enumeration is over all subsets of the middle ones and doubles with each place added. Sixteen cuts is a table; a network with twenty places has half a million, and the exhaustive check that makes these figures honest stops being available almost immediately.

That is a real limit on the method rather than on the theorem. What the drawings establish is that the equality holds on the networks drawn; the proof is what establishes it in general, and no drawing can substitute.

The flow itself is found by pushing along routes with room left, and the drawings say nothing about how many pushes that took or whether a different order would have found a different flow. A maximum flow is generally not unique — several routings achieve the same value — while the value is, and the minimum cut may not be unique either. The figures show one of each and claim only what they check.

The ladder from here #

Below: one bottleneck and nothing else, the matching case with its own proof, and seven bridges, where a network’s structure first decides what is possible. Sideways: two numbers that have to meet and what a constraint is worth, the linear-programming duality this is a special case of, and the value from both sides, the same min-max shape in a game. Above: Menger’s vertex version, the integrality theorem, flows with lower bounds and costs, and the failure of the equality for more than one commodity.

What is worth carrying away #

Two quantities defined by completely different means — a maximum over ways of routing, a minimum over ways of severing — turn out to be one number. Each is easy to bound in one direction and hard in the other, and putting them together makes both easy.

The general shape is worth carrying past this subject. Whenever a maximisation has a natural dual minimisation, the first thing to ask is whether they meet, because if they do, every optimum comes with a certificate and every claim of optimality becomes checkable. When they do not meet — and for multi-commodity flow they do not — the gap between them is itself an object worth measuring, and the subject changes character entirely.