Motivation
A network can have abundant capacity leaving its source and still carry little to its destination: a bottleneck farther downstream may limit every route. A flow assigns compatible quantities to edges, while a cut certifies an upper bound on every possible flow. The residual network connects the two viewpoints: it tells us both how to improve a candidate and why no improvement remains.
Definitions
Definition 3.1.1
(Flow, value and cut)
Let be a finite directed graph, with distinct source and sink , and capacities . For simplicity, use one directed edge per ordered pair; opposite directed edges are allowed. A flow assigns and satisfies conservation at each vertex other than : incoming flow equals outgoing flow. Its value is net outflow at . An – cut is a partition with , ; its capacity is the sum of capacities of original edges from to .
Definition 3.1.2
(Residual network and augmenting path)
For each original edge , the residual network has a forward arc of capacity and a reverse arc of capacity , retaining only positive-capacity arcs. Reverse arcs represent permission to cancel earlier flow, not additional original capacity. If opposite original edges yield parallel residual arcs, retain their identities: augmenting along one modifies its own original edge. An augmenting path is a directed residual – path; its bottleneck is the minimum residual capacity on that path.
Theorems
Theorem 3.1.3
(Flow–cut equality and optimality)
For every feasible flow and – cut , . A feasible flow is maximum exactly when its residual network has no augmenting path. In that case the vertices reachable from in the residual network give a cut with capacity .
Theorem 3.1.4
(Integral augmentation)
If all capacities are nonnegative integers, starting from the zero flow and repeatedly augmenting on any residual path by its bottleneck terminates with an integral maximum flow. If is the sum of capacities of edges leaving , there are at most augmentations. This bound is in the numeric value of , not necessarily polynomial in its binary encoding length.
Proof sketch or proof idea
Proof
(Weak duality: every cut bounds every flow)
Sum conservation over vertices in except . Internal edges cancel, yielding . This proves weak duality: any cut bounds any flow.
Proof
(Augmenting along a residual path)
Along a residual path, increase original-edge flow when using a forward arc and decrease it when using a reverse arc. The bottleneck keeps every modified flow within its bounds. Each internal path vertex receives and sends the same increment, including when an arc cancels an original edge, so conservation remains true and the net value increases by the bottleneck. Thus a flow with an augmenting path is not maximum.
Proof
(No augmenting path gives an equal cut)
If no path exists, let be the reachable vertices and the rest. Every original edge from to is saturated; otherwise its forward residual arc reaches . Every original edge from to carries zero; otherwise its reverse residual arc reaches . Hence the cut identity becomes . Weak duality now shows both that is maximum and that this cut is minimum. This also proves the converse: a maximum flow has no augmenting path.
Proof X-ray
A certificate, not a guess
The optimality proof turns a failed search into a cut. The set of reachable vertices is closed under residual arcs by construction, and that closure is the only property used: no positive residual arc leaves . Unwinding it edge by edge gives the two equalities needed. An original edge from to with spare capacity would give a positive forward arc leaving , so every such edge is saturated. An original edge from to with positive flow would give a positive reverse arc leaving , so every such edge carries zero. The identity then reads . Weak duality, proved from conservation, finishes the argument: no flow can exceed this cut, and no cut can lie below this flow. Without reverse arcs the second equality would be lost and a search could stop at a flow that is not maximum, which is why the early choice in the canceling example must be reversible.
Proof
(Integral capacities give termination)
For integral capacities, initially zero flow is integral and all residual capacities remain integral. Every augmentation has positive integer bottleneck and increases value by at least one. The cut bounds the value by , so the process stops after at most iterations and optimality follows. A breadth-first choice of shortest augmenting paths admits a polynomial bound independent of numeric capacity, but that separate bound is not proved here.
Worked examples
Worked example 3.1.5
(Two routes and a bottleneck)
Let capacities be , , , , . Send along and along ; then send along . The flow has value . The cut has capacity , proving optimality.
Worked example 3.1.6
(Canceling an early choice)
Let all capacities be on , , , , . If the first path is , the direct forward route from through is saturated. The residual path uses the reverse of . Augmenting cancels that edge's flow and leaves one unit along each of and . The resulting value equals the source cut.
Worked example 3.1.7
(A cut bound with a backward edge)
Suppose a cut has forward capacity and current forward flow , but also carries units of original flow from back to . Its net contribution to the flow value is , not . Summing only forward flow would overstate the value. The identity includes both directions even when an optimal flow happens to have no backward flow across its certifying cut.
Common mistakes
Common mistake
(Residual capacity is not original capacity)
A reverse arc of capacity one can appear even when the original graph has no edge in that direction. It permits canceling one unit previously sent; it does not permit sending unlimited new flow on a nonexistent edge.
Counterexample mode
Arbitrary augmenting paths can use the whole bound
Consider the claim that augmenting along arbitrary residual paths takes only polynomially many steps in the size of the input. Let be a positive integer. Take edges , , and of capacity and an edge of capacity , so . Augment alternately along and along , the second path using the reverse of . Each path has bottleneck one, each augmentation raises the value by exactly one, and the value is reached only after augmentations. The bound is attained, and the number of steps grows with , which is exponential in the number of bits of . The repaired claim restricts the choice of path, for example to breadth-first shortest paths, whose polynomial bound is a separate result.
Common mistake
(Blocked chosen paths do not mean no path)
Stopping because the currently chosen paths are blocked is insufficient: a different residual path may reroute earlier choices. The algorithm must search the whole residual network. For real capacities, the weak-duality and no-path certificate remain valid, but the integer termination proof does not apply to arbitrary path choices.
From a procedure to a certificate
A residual search should store not only that a vertex was reached, but also the predecessor arc by which it was reached. If is reached, tracing predecessors back to recovers a path and its bottleneck. If the search ends without reaching , its visited set is exactly the side of the optimality certificate. In either case the same search gives the next object needed by the proof. Care is needed to retain the identity and direction of each residual arc, especially when the original graph has edges in both directions: an arc from to may either increase flow or cancel some flow.
For example, if , , and , there are two residual opportunities from to : increase the first edge by at most , or cancel the second by at most . They have the same endpoints but different updates. Combining their numerical capacities is possible only if the implementation also chooses a valid decomposition when it updates the original edges. Retaining parallel labeled arcs avoids that additional bookkeeping.
The cut identity also clarifies what equality requires. In
every difference in the forward sum and every backward flow is nonnegative. Equality occurs exactly when all forward cut edges are saturated and all backward cut edges have zero flow. This condition can certify optimality for any given feasible flow and cut, without assuming how the flow was constructed. It also explains why the reachability cut works: a positive residual arc crossing from to would contradict the definition of .
Worked example 3.1.8
(A flow and cut as independent certificates)
Consider capacities , , , , . Assign flows respectively. At the proposed inflow is but the outflow is , so this assignment is not a flow at all. Correct it by increasing to . The value becomes and conservation holds: at , and at . The cut has capacity , so the corrected flow is maximum. Checking the cut before checking conservation would have concealed the original error.
Modeling limits
Capacities are upper bounds, not demands that each edge must be used. Conservation applies at intermediate vertices, while source and sink can have incoming and outgoing edges; this is why the value is defined as net outflow. A positive circulation around a directed cycle changes individual edge flows without changing the value. Therefore a maximum flow need not be unique, even when the maximum value is unique. It is also unnecessary for an optimal solution to use every available edge.
The theorem permits zero capacities and the zero flow. If no directed path from to has positive capacity, the initial residual search produces a cut of capacity zero, and zero is already optimal. Conversely, a path may exist while the value is small: path existence only ensures some positive augmentation, not a bound on the total. For integer data, the bound counts the number of augmentations in the worst case; if capacities are encoded in binary, a number with bits can be as large as . Consequently the bound alone does not establish polynomial running time in the input length.
An application: bipartite matching
For a bipartite graph with left vertices and right vertices , construct a network with unit edges from to every left vertex, directed unit edges from to for each graph edge, and unit edges from every right vertex to . An integral flow decomposes here into chosen left–right edges: conservation and unit source/sink edges ensure that no vertex is used more than once. Conversely, send one unit along for every edge in a matching. Thus the maximum flow value equals the maximum matching size. The integrality theorem is essential to reading edge flows as actual yes-or-no matching choices; a generic fractional feasible flow cannot simply be called a matching.
For example, with , and edges –, –, –, choosing – first may block a direct choice for . The residual path cancels the earlier – choice and replaces it with – and –. This is the matching version of rerouting flow. The cut containing only has capacity two, establishing optimality of the resulting size-two matching.
Checking a proposed solution
A practical verification order is to check edge bounds first, then conservation, then the claimed value, and only then compare with a cut. All four steps matter. A flow with value larger than a proposed cut cannot be a counterexample to weak duality: at least one of those checks must have failed. For a numerical certificate, write the flow on every edge, including zeros, and list all original edges crossing the cut in the forward direction. The reverse crossing edges enter the flow identity but not the definition of cut capacity. For an equal-value certificate, they must in fact have zero flow.
A residual path is a sequence of residual arcs, not necessarily a sequence of forward original edges. A simple path can be found whenever any residual walk reaches the sink, because repeated vertices may be removed from a walk. If a path uses a reverse arc for an edge already carrying three units, the augmentation cannot cancel more than those three units. If two is the smallest residual capacity of the other arcs on that same path, the bottleneck is two, so the algorithm changes every arc by two and leaves the canceled edge with one unit. Choosing a larger increment would violate at least one capacity or nonnegativity constraint.
The integer augmentation bound does not require each individual edge flow to increase monotonically. Reverse residual arcs can decrease a previously assigned flow, as in the matching example. What increases monotonically is the net value of the whole flow. Since the value is an integer and a fixed cut bounds it, that monotonic quantity is sufficient to prove termination. This is a common proof pattern in algorithms: the potential that establishes progress may be different from the local variables modified at each step.
Finally, the min-cut statement provides sensitivity information. If a particular cut has capacity six, adding capacity to an edge that does not cross that cut cannot by itself raise the maximum above six, because the same cut remains an upper bound. Increasing an edge that does cross a minimum cut may raise the bound, but does not guarantee that the maximum rises: another minimum cut may remain unchanged. Recompute or provide a new equal flow–cut certificate before asserting an improvement.
Summary
Flow conservation turns every cut into an upper bound. Residual paths improve feasible flows, while the absence of such a path constructs an equal-capacity cut. Integral capacities guarantee integral flows and a finite augmentation procedure, with a potentially pseudopolynomial iteration bound.
Exercises
Quick check
(In the first example, verify conservation at and after all three augmentations.)
Add the flow on the edges entering and leaving each vertex.
Solution · Answer
At , inflow equals outflow . At , inflow equals outflow . All used edge flows respect their capacities.
Quick check
(A feasible flow has value and a cut has capacity . What follows, and why?)
Compare each with weak duality.
Solution · Answer
Weak duality bounds every flow by and every cut from below by , so the displayed flow is maximum and the cut is minimum.
Quick check
(With integer capacities and , how many arbitrary-path augmentations can the algorithm perform at most?)
Each augmentation raises the integral value by at least one.
Solution · Answer
At most : each augmentation increases an integral flow value by at least one, while the source cut bounds the value by .
Quick check
(A network has capacity and capacity , with no other edges. Find a maximum flow and a minimum cut.)
Find the bottleneck on the only path.
Solution · Answer
Send units along the path. The cut has capacity , proving optimality. The unused units of source-edge capacity cannot cross the bottleneck.