Motivation
A network may have enough total capacity leaving its source and still fail to carry that much to its destination. Somewhere between them, a collection of arcs forms a bottleneck. Finding a large feasible flow gives a lower bound on what can be transported; finding a small separating cut gives an upper bound. When the bounds agree, optimality is proved.
The important difficulty is that an early routing choice may need to be undone. A residual network records both unused capacity and the ability to cancel flow already sent. This is the directed analogue of reversing matching edges along an augmenting path. Ignoring the cancellation arcs can make an algorithm stop at a flow that is far from maximum.
Definitions
Definition 7.1.1
(Flows and their value)
A finite directed network has distinct source and sink vertices , no loops, and a nonnegative capacity on each arc . Opposite directed arcs are allowed and remain distinct. A feasible flow assigns and satisfies conservation at every vertex other than : total incoming flow equals total outgoing flow. Its value is
A source–sink cut is a partition of all vertices with . Its capacity is ; arcs in the reverse direction are not included in this sum.
Definition 7.1.2
(Residual arcs retain their original labels)
For each original arc , its forward residual arc has direction and capacity ; its backward residual arc has direction and capacity . Keep only positive-capacity residual arcs when searching. Each residual arc remembers the original arc and whether to increase or decrease its flow. Thus different residual arcs may have the same endpoints, especially when the original network has opposite arcs.
A residual augmenting path is a simple directed path from to . Its bottleneck is the smallest residual capacity on its arcs. Increasing original flow along forward arcs and decreasing it along backward arcs by that bottleneck is augmentation. The original capacities and flows remain attached to their original directed arcs; a backward residual arc is an instruction, not a newly installed transport arc.
Theorem/Proposition
Theorem 7.1.3
(Every cut bounds every feasible flow)
For every feasible flow and every source–sink cut,
Equality holds exactly when every original arc from to is saturated and every original arc from to carries zero flow.
Theorem 7.1.4
(Residual augmentation and the cut certificate)
Augmenting along a residual path by its positive bottleneck preserves feasibility and increases the flow value by that amount. If no residual source–sink path exists, the vertices reachable from form a cut whose capacity equals the current flow value. Hence the current flow is maximum and that cut is minimum.
Theorem 7.1.5
(Integral max-flow min-cut)
If all capacities are nonnegative integers, a maximum flow exists with integer arc values, and its value equals the minimum cut capacity. Starting from zero and repeatedly augmenting along any residual source–sink path terminates after at most augmentations. When , it stops immediately.
Proof sketch or proof idea
Proof
(Summing conservation over the source side)
Sum outgoing-minus-incoming flow over vertices of . Internal arcs appear once with each sign and cancel. Conservation removes every vertex contribution except that of , leaving exactly the displayed net flow across the cut. Subtract this net flow from the cut capacity. The difference is the sum of unused capacity on outward arcs plus flow on inward arcs. Every term is nonnegative, proving the bound and its equality conditions.
Proof
(Augmentation preserves feasibility; a stuck search yields a tight cut)
For augmentation, the bottleneck is no larger than any forward unused capacity or backward existing flow on the path. All updated original values therefore stay between zero and capacity. Every internal path vertex has one residual arc arriving and one leaving. Whether an instruction increases a forward arc or decreases a backward arc, it changes the vertex's net outgoing flow in the residual direction. The two changes cancel internally, while the source gains the bottleneck and the sink loses it. Thus conservation and the value claim follow. Simplicity prevents the same original arc being used in both directions on one path.
Suppose there is no residual path to , and let be the residual-reachable vertices. The sink is outside . Every original outward arc must be saturated: otherwise its positive forward residual arc would reach outside. Every original inward arc must carry zero: otherwise its positive backward residual arc would also leave . The equality conditions in the first theorem give . The universal cut bound then certifies both optima.
Proof X-ray
Reading the cut off a failed search
The decisive move is that the cut is not chosen in advance: it is read off the residual search as the set of vertices reachable from . Two kinds of residual arc then do separate jobs. Forward residual arcs force every original arc from to to be saturated; backward residual arcs force every original arc from to to carry zero flow. Both are needed, because the equality case of the cut bound has two conditions.
In the first worked example, after one unit on , a search that ignores backward arcs reaches exactly . Its outward arcs and are saturated, so this cut has capacity two, while the flow has value one, because the inward arc still carries a unit. The backward arc is what lets the search continue. The argument closes through the universal bound: a flow of value cannot be beaten, and a cut of capacity cannot be undercut, so both are optimal at once. Integrality plays no role here; it enters only in the termination proof, where each augmentation raises an integer value by at least one below the finite ceiling .
Proof
(Integral steps below the source-cut ceiling)
Finally start with zero flow and integral capacities. All residual capacities and bottlenecks remain integers, so every augmentation increases the integral value by at least one. The cut consisting of the source alone bounds the value by . Hence at most augmentations occur, and a residual search must eventually fail. The preceding cut certificate then proves existence of an integral optimum and the equality of optimum values. This argument proves termination for integral capacities; it does not justify arbitrary-path termination for unrestricted real capacities.
Worked examples
Worked example 7.1.6
(A backward arc repairs an early routing choice)
Give capacity one to , with each two-letter label directed from its first vertex to its second. First send one unit along . A second original-only path cannot be found, but the residual path exists. Its arc cancels the earlier unit on . The result routes one unit through and one through , for value two. The source cut has capacity two, proving optimality.
Worked example 7.1.7
(A cut proves that a value below source capacity is optimal)
Take capacities . The flow is feasible: vertex has three units in and three out; has four in and four out. Its value is six. The cut has outward capacity , so this is maximum. Total source capacity is seven, which is only an upper bound and is not attained.
Worked example 7.1.8
(A numerical bound need not be polynomial in input length)
Give arcs capacity and arc capacity one. Repeatedly choose residual paths and . The second cancels the first path's unit on . Each pair increases both direct branch flows by one and restores . It takes augmentations to reach value , although needs only binary digits. The termination bound is valid but can be exponential in encoded input length for these path choices.
Why reverse residual capacity equals existing flow
A forward instruction spends unused capacity, while a backward instruction removes already committed flow. One cannot cancel more than was previously sent, which is why the backward capacity is exactly the existing original flow. After cancellation, the original flow remains nonnegative; after a forward increase, it remains below its original capacity. These two bounds are the local feasibility proof.
When an original reverse-direction arc also exists, it supplies a separate possible action. Traversing its forward residual arc sends new flow in that direction. Traversing the backward residual arc of the opposite original arc cancels old flow. The two actions can have different available amounts and change different original variables. A labeled residual representation distinguishes them without ambiguity. One may combine their capacities in a carefully designed implementation, but the proof must still explain which original flows are changed.
The residual graph also changes after every augmentation. A previously absent backward arc may become available, and a previously available forward arc may disappear when saturated. Searching only the initial residual graph would therefore miss legitimate repairs. The search is a property of the current flow state.
Source and sink bookkeeping
Flow value is net outgoing source flow, not merely the sum on outgoing arcs when incoming arcs are allowed. The cut identity automatically accounts for this. Taking the source side to be every vertex except the sink also shows that the value equals net incoming sink flow. Conservation across all other vertices is what makes the two descriptions agree.
A feasible flow may contain a directed circulation that carries no extra source–sink value. Such a circulation is not a proof of a larger optimum; its contributions cancel across every cut. Conversely, a maximum flow need not be unique, and its detailed routing is not determined by a minimum cut. The theorem equates optimum values, not individual flow configurations or unique bottlenecks.
Matching as a unit-capacity routing problem
For a bipartite graph with parts , add a source with capacity-one arcs to every left vertex and capacity-one arcs from every right vertex to a new sink. Direct each graph edge from left to right and give it capacity . A matching produces an integral flow by sending one unit along each of its source–left–right–sink paths.
Conversely, an integral feasible flow uses at most one unit leaving any left vertex, because its only incoming arc has capacity one. It uses at most one unit entering any right vertex for the analogous reason. Its positive middle arcs therefore form a matching, and their number equals the flow value. Integral max-flow existence establishes equality between maximum matching size and maximum flow value in this constructed network.
The large finite middle capacity also makes a minimum cut describe a vertex cover. The source-alone cut has capacity , so a minimum cut cannot cross a middle arc of capacity . Thus every original edge has its left endpoint on the sink side or its right endpoint on the source side. Those vertices form a cover, and its size is precisely the cut capacity from the unit boundary arcs. This gives a second route to matching–cover equality and explains why a finite large capacity is sufficient; no literal infinity is required.
Concept lensStructural
Alternating paths are residual paths in disguise
A selected matching edge carries one unit on its middle arc, so its residual backward direction permits removing that assignment. An unselected edge permits adding one. A source–sink residual path therefore traces exactly the reassignment mechanism of an augmenting path. The larger flow framework retains the same idea while allowing capacities above one.
What the elementary algorithm's cost statement means
A residual search can be implemented using adjacency lists in time proportional to the number of vertices plus original arcs, since every original arc contributes at most two residual instructions. Combining this with the integral augmentation bound gives operations for this elementary method. The parameter is a capacity value, not its binary length.
The third example shows that this distinction is operational, not merely a loose bound. Different path-selection rules can improve performance substantially, but those improvements require a further analysis. The present proof establishes correctness, a capacity-dependent termination bound and integral optimum existence. It does not establish a strongly polynomial algorithm.
Common mistakes
Common mistake
(Stopping when no original path has spare capacity)
A saturated original source–sink path does not certify optimality. Other paths or residual reversals may improve the flow: in the first worked example no original path is left after , yet the value can still be doubled. A matching likewise may require exchanging edges rather than adding one; both failures come from refusing to reconsider earlier decisions.
Counterexample mode
Integral capacities do not force every optimum to be integral
Let arcs all have capacity one. Send one unit on and half a unit along each of and . This fractional flow has value one, equal to the source cut, and is maximum. An integral optimum also exists by using only the branch through . The integrality theorem asserts existence of an integral optimum, not integrality of every feasible or optimal flow.
Common mistake
(Miscounting arcs that enter the cut)
Do not count arcs entering a cut as positive capacity in the cut bound. Their flows subtract from the net value. Likewise an outward saturated cut alone does not prove equality if inward arcs still carry positive flow; both equality conditions are needed.
Summary
Residual arcs encode both spare capacity and reversible decisions. Augmentation preserves feasibility, and a failed residual search produces a cut of exactly the attained value. Integral capacities make arbitrary-path augmentation terminate and yield an integral optimum. Capacity-dependent runtime and binary-input complexity remain distinct claims.
Exercises
Quick check
(For capacities , , , , , find a maximum flow and list all minimum cuts.)
There are only four possible source sides in this four-vertex network.
Solution · Answer
Use flows . Conservation holds and the value is five. Source sides , and have capacities five, five and five. The remaining possibility has capacity six. The universal cut bound proves maximum value five, and enumeration gives exactly those three minimum cuts.
Quick check
(In the matching reduction, explain why using capacity one on middle arcs still represents matching values but may prevent a minimum cut from directly giving the stated vertex cover.)
Use a graph with one edge.
Solution · Answer
With one left vertex , one right vertex and edge , unit middle capacity gives a network whose maximum flow is one. The cut with source side crosses only the middle arc and is minimum. Yet the proposed cover consisting of sink-side left vertices and source-side right vertices is empty, so it misses . Taking middle capacity excludes this cut from the minimum and restores the cover argument.
Quick check
(Prove that if a feasible flow equals the capacity of a cut, then every outward arc is saturated and every inward arc has zero flow.)
Explain why cancellation between error terms cannot invalidate the conclusion.
Solution · Answer
Subtract the cut identity from the capacity: the difference is . Every term is nonnegative by feasibility. Equality makes their finite sum zero, so every term separately vanishes. There can be no cancellation between positive and negative terms because no negative terms occur. Thus the two claimed conditions follow.