Maximum Flow Equals Minimum Cut: Proof by Example

Here is a question with a genuinely beautiful answer. You have a network of pipes, and every pipe has a limit on how much it can carry. You want to push as much as possible from one end of the thing to the other. How much can you push, and how would you ever prove that you cannot do better? This is the network we will work with for the whole lecture. There are four nodes in it. s is the source, where everything starts, and t is the sink, where everything has to end up. In between sit two junctions, called a and b. Five directed edges join them up. The gray number on each edge is its capacity, the most that edge could ever carry. The green number beside it is how much is flowing along it right now, which for the moment is nothing at all. Read the capacities off. The source can send three units into a, and four into b. The edge from a down to b can carry two. And into the sink, a to t can carry two, and b to t can carry three. The arrows matter. An edge from a to b is not an edge from b to a, and that capacity of two is a limit on units travelling downward only. Nothing at all is allowed to travel back up it. A flow is an assignment of a number to every edge, and it has to obey two rules. The first one is obvious. No edge may carry more than its capacity, and no edge may carry a negative amount. The second rule is conservation. At every node except the source and the sink, whatever flows in has to flow out again. A junction does not store anything, and it does not invent anything either. Let me push something through, so you can watch both rules working. Send two units out of the source along the top edge into a. Now a has two units arriving and nothing leaving, which breaks conservation. So send them onward. One unit goes down to b, and one goes straight across to the sink. And b has one unit arriving, so one unit leaves for the sink. Every junction balances now, no edge is over its capacity, and what you are looking at is a perfectly legal flow. Its value is simply what leaves the source, which here is two units. The two units arriving at the sink agree with that, and they always will, because nothing is created or destroyed in the middle. It is not a very good flow. The edge from the source into b is carrying nothing whatsoever, and the edge out of b has two units of room going spare. We are going to do considerably better than this. Now the other half of the story, and it is the half that does the proving. Take any way at all of splitting the four nodes into two groups, with the source in one group and the sink in the other. That is called a cut. Here is the simplest one there is. Draw a line just to the right of the source, so that the source is on its own and a, b and the sink are together on the far side. Two edges cross it, s to a and s to b. The capacity of a cut is the total capacity of the edges crossing it forwards. Three plus four is seven, so this particular cut has capacity seven. And here is why that matters so much. Every single unit of flow begins at the source, on the left of that line, and ends at the sink, on the right of it. So every unit has to cross somewhere, and the value of the flow can never be more than seven. That is worth saying twice, because the entire proof rests on it. A cut is a wall. Whatever the flow does, however cleverly it is routed, it has to get through the wall, and the wall has a fixed total width. Try a different one. Move the line over to the far side, so that the source, a and b are together and only the sink is on its own. Now the crossing edges are a to t and b to t. Their capacities are two and three, so this cut has capacity five. Five is a far better piece of information than seven was, because it says the flow can never get past five. A network this small has only four cuts, one for each way of deciding which junctions go on the source side. The other two come out at eight and at six. So five is the best ceiling any cut here can give us. So every cut hands us a ceiling, and the smallest cut hands us the best ceiling this kind of argument could ever produce. The theorem we are going to prove says something much stronger than that. The best ceiling is always reached exactly. Maximum flow equals minimum cut. Not at most. Equal. In a few minutes you will watch the flow climb to five, and then watch a cut of capacity five appear out of the leftovers, and the two numbers will meet in the middle.

We have a network, and we have the rules a flow has to obey. What we need now is a way to actually find the biggest flow, and the method is almost embarrassingly simple. Find a route from the source to the sink that still has room on every edge, and push as much along it as the tightest edge will allow. A route like that has a name. It is called an augmenting path, because sending flow along it augments what we already have. The amount it can take is decided by whichever edge has the least room left, and that edge is called the bottleneck. Nothing is flowing yet, so every edge has all of its room available. Take the top edge into a, then the edge down to b, then out of b to the sink. The room on those three edges is three, then two, then three. The smallest is two, so two units is everything this path can carry. Push it through. All three edges on the path go up by two, and the flow we are holding now has value two. Now look at the middle edge. Two units on a capacity of two, which means it is completely full. Nothing more can ever go along it while this flow stands. Look for another path. From the source into a there is one unit of room left, and from a straight across to the sink there are two units. The bottleneck is one, so one unit is what we send. Three units are leaving the source now. And the edge out of the source into a is full as well, three out of three, with nothing to spare. One more path. From the source into b there is plenty of room, three units of it. But the edge from b to the sink has only one unit left, so one unit is all we can send along this one. Four units. And now we are stuck. Look at what is left. The edge from the source to a is full, so a cannot be reached that way at all. The edge from the source to b does have room, so we can get as far as b. But b to t is full, and b has no other edge leading forward. There is nowhere to go. So the simple method has run out of paths at a value of four. And the uncomfortable question is whether four really is the answer, or whether we made a bad choice somewhere and the method has no way at all of noticing. We did make a bad choice, and it was the very first path. Those two units went from a down into b, and then out of b to the sink, and between them they used up nearly the whole edge into the sink. But b had a supply of its own, coming straight from the source, and now there is no room left for it. The two units that came down from a squeezed it out. What we would like to do is take one of those two units back off the edge from a to b, push it across from a to the sink instead, and let a unit from the source into b move into the space it leaves behind. But the method as we stated it cannot walk backwards. So we change what the method is allowed to walk on. This is the residual graph, and it records not what is flowing, but what could still change. Forwards, it is what you would expect. An edge of capacity four carrying one unit has three units of room, so three more could still be pushed along it. Every number on the picture is already telling you that. Backwards is the new idea. An edge carrying one unit could have that unit taken away again, so the residual graph also holds a reverse arrow along it, pointing back the way the flow came, with capacity equal to the flow currently on the edge. Here they all are, one for every edge that is carrying something. Most of them are no use to us. These two come out of the sink, and these two point back at the source, and reaching them gets us nowhere new. This one is the one that matters. Two units are currently running from a down to b, so the residual graph offers two units of capacity going the other way, from b back up to a. Now search again, and this time walk on residual edges. From the source into b there is room. From b, take the backward arrow up to a. And from a there is one unit of room left into the sink. That is a path from the source to the sink: s, then b, then a, then t. Its bottleneck is one unit, so one unit is what we push along it. The edge from the source into b goes up to two. The edge from a to b is walked backwards, so it goes down by one, from two to one. And the edge from a to the sink goes up to two. The value is five. So check that nothing has broken. At a, three units arrive from the source, one leaves downward into b, and two leave across to the sink. Three in and three out. At b, two units arrive from the source and one arrives from a, and three leave for the sink. Three in and three out again. Every capacity is respected, and this is a perfectly legal flow of value five. And look at what the backward step actually did to the picture. It did not cancel the first path, and it did not throw anything away. One unit that used to go source, a, b, sink now travels source, a, sink. And one unit that previously had nowhere to go now travels source, b, sink. The bookkeeping did the rerouting for us. Nobody had to spot that swap in advance, and nobody had to go back and edit an earlier decision. The backward arrow made an old choice reversible, and the search took the reversal without knowing it was being clever. That is the whole algorithm. Find a path in the residual graph, push the bottleneck along it, rebuild the residual graph, and repeat until there is no path left. It is called Ford Fulkerson. Which leaves exactly one question. When it stops, has it actually won? Or is there some cleverer route that this procedure simply cannot see?

Here is the flow we finished with. Five units, and every number on it is the number we left it at. The question now is not how to improve it. The question is how to be certain that nobody can. So run the search one more time, and this time watch where it can get to, rather than whether it finishes. Start at the source, and mark every node the residual graph can still reach. From the source, the edge to a is full, three units on a capacity of three, so there is no room that way. The edge to b carries two units on a capacity of four, so it has two units of room, and b is reachable. From b, the edge to the sink is full as well, three on three. But one unit is currently flowing from a down into b, so the residual graph has a backward arrow there. Walk it, and a is reachable too. And from a, the edge to the sink carries two units on a capacity of two. Full. So the search stops there, with the source, a and b all marked, and the sink not marked at all. Call that set of marked nodes S. It contains the source by construction. And it does not contain the sink, because if it did we would have found an augmenting path, and we would not have stopped. So S and everything outside it form a cut, and we already know how to price a cut. The edges crossing forwards out of S are a to t, with capacity two, and b to t, with capacity three. Two plus three is five. The cut has capacity five. And the flow has value five. The ceiling we could never beat, and the flow we actually built, are the same number. That is not a coincidence, and the reason is worth seeing properly, because the reason is the whole proof. Take any edge that crosses forwards out of S, from a marked node to an unmarked one. It has to be completely full. Because if it had any room left on it at all, the search would have walked along it, and the node at the far end would have been marked as well. It is not marked. So the edge is full. Now take an edge crossing the other way, from an unmarked node back into S. That one has to be completely empty. Because if it were carrying anything, the residual graph would hold a backward arrow along it, running from the marked end to the unmarked end, and the search would have crossed that arrow instead. Again, it did not. In this particular network there is nothing to check on that side, because nothing at all leaves the sink. But that half of the argument is exactly what makes the general theorem work. So put the two halves together. The value of a flow is what crosses the cut forwards, minus whatever crosses back. Forwards, every crossing edge is full, so that first sum is the entire capacity of the cut. Backwards, every crossing edge is empty, so nothing whatsoever is subtracted. So the value of the flow is exactly the capacity of this cut. And we already knew that no flow anywhere can exceed the capacity of any cut. Two facts, and between them they nail the answer down completely. No flow can beat five, because this cut has capacity five and our flow reaches five. So our flow is a maximum flow. And no cut can dip below five, because the flow has value five and this cut achieves it. So this cut is a minimum cut. Maximum flow equals minimum cut. And notice how it arrived. We never went looking for the cut. We ran out of augmenting paths, and the cut was already sitting there in the leftovers, made of exactly the nodes the search could still see. That is a genuinely useful property of the algorithm, and not just a pretty fact. When it stops, it hands you a certificate. Anyone who doubts that five is the best possible can be shown two edges, of total capacity five, that every single unit has to cross. One more thing before we finish, because this theorem turns up in places that have nothing obvious to do with pipes at all.

Here are three people, and three jobs, and a line whenever a person is able to do a job. The problem is to give as many people as possible a job of their own, with nobody sharing. The lines say who can do what. Person one is able to take either the first job or the second. Person two is qualified for the first job alone. And person three can take the second job or the third. This is bipartite matching, and it looks like a completely different kind of question from pushing water down pipes. It is exactly the same question. Add a source on the left, joined to every person. Add a sink on the right, joined to every job. And give every edge in the whole picture a capacity of one. Now push flow through it. A unit of flow leaving the source has to pick one person, because that person's own edge from the source has capacity one and can carry nothing more. It then crosses to a job that person can do, and leaves through that job's edge to the sink, which also has capacity one. So one unit of flow is exactly one person doing one job, and no job can ever be taken twice. The value of the flow is the size of the matching. Maximum flow is maximum matching, and it is the same algorithm, completely unchanged. Now watch the same mistake happen again. Send the first unit through person one to job one. And send a second unit through person three to job three. Now person two. The only job on their list is job one, and job one is taken. Greedy stops with two people placed and one left out in the cold. But the residual graph has a backward arrow on the edge from person one to job one, because that edge is carrying a unit. Follow it. From the source to person two. Across to job one. Backwards up to person one. Across to job two, which nobody has taken. And out to the sink. Push one unit along that path, and the picture rearranges itself. Person one moves over to job two. Person two takes job one. And person three keeps job three. Three people, three jobs, and nobody sharing. The backward edge did exactly what a person would do out loud. You take that one, and I will take another. And the minimum cut says something too. When a matching cannot cover everybody, the cut tells you why. It exhibits a set of people whose lists of jobs, taken together, are simply too short to go round. That is Hall's condition, and it falls straight out of the theorem we have just proved. So there it is. Push flow along augmenting paths. When you get stuck, let the residual graph undo an earlier decision. And when even that runs out, the nodes you can still reach form a cut, its capacity equals the flow you are holding, and neither number can move any further. Maximum flow equals minimum cut.