This section treats two central network optimization problems, maximum flow and shortest paths, through their models and certificates. Linear programming vocabulary is useful, but the proofs below use graph arguments directly.
Motivation
A communication network raises two different questions. How much information can cross the network per unit time when links have limited capacities? Which route has smallest total delay when each link has a specified length? The first asks for many simultaneous routes; the second asks for one cheapest route. A narrow link can restrict throughput even if it is fast, and a high-capacity link can be unattractive for a shortest route. Keeping these objectives separate prevents an intuitive picture from silently changing the problem.
Networks also explain why a greedy decision may need revision. Sending a unit along one route can block two later routes. The right response is not necessarily to erase the whole calculation. A residual network records exactly how much of each previous decision can be increased or canceled. This turns revision into another path search.
Both problems admit short verifiable evidence. A flow and a cut of equal value prove maximum throughput. A route and a feasible distance potential of equal value prove minimum length. The certificate can be checked independently of the algorithm that found it, which is particularly valuable when a large computation is difficult to inspect step by step.
Definitions
Definition 2.1.1
(Directed flow, value, and cuts)
Let be a finite directed graph with distinct source and sink . Each labeled arc has finite capacity . A feasible flow assigns and satisfies conservation at every vertex other than : total inflow equals total outflow. Its value is net outflow from the source,
An - cut is a set containing but not . Its capacity is the sum of capacities of arcs from to .
Oppositely directed original arcs are allowed and retain separate labels. For each original arc , the residual network contains a forward arc from to of residual capacity and a backward arc from to of residual capacity , whenever the corresponding quantity is positive. A backward residual arc authorizes reducing that original flow; it is not a claim that the original network contains a physical reverse link.
An augmenting path is a directed source-to-sink path in this residual network. Its bottleneck is the least residual capacity along the path. Adding that amount on forward arcs and subtracting it on backward arcs produces a new flow. Retaining labels matters when several residual arcs connect the same ordered pair: they may represent different changes to different original variables.
For shortest paths, attach a real length to each arc. The length of a walk is the sum of its arc lengths with repetitions counted. A path has no repeated vertices. A distance potential is a real number at every vertex satisfying and on every arc. The potential measures a lower bound on the length of reaching a vertex; it is not itself a selected route.
Theorem/proposition
Theorem 2.1.2
(Maximum flow equals minimum cut)
For a finite network with finite nonnegative capacities, a maximum feasible flow exists, and its value equals the least cut capacity. A feasible flow is maximum exactly when its residual network has no augmenting path. If all capacities are integers, there is an integer-valued maximum flow.
The theorem establishes existence even for real capacities. A particular path-selection algorithm need not terminate for arbitrary irrational capacities. The integer termination argument below applies to integer capacities, and scaled versions apply to rational capacities. These algorithmic qualifications do not weaken the cut certificate.
Proposition 2.1.3
(Shortest-path potential certificate)
Let be a distance potential. Every directed walk from to has length at least . If one - path uses only tight arcs, meaning on each of its arcs, its length is and it is shortest among all such walks.
A feasible potential also rules out a negative-length directed cycle anywhere in the graph: summing its inequalities around that cycle would show that zero is at most a negative number. Such a global potential therefore may not exist when a disconnected irrelevant component contains a negative cycle. One may restrict attention to the vertices reachable from the source when computing source distances. For a particular target, a reachable negative cycle makes walk lengths unbounded below only if that cycle can also reach the target.
Proof sketch or proof idea
Proof
(Cuts bound flows, and a reachability cut attains the bound)
Sum flow conservation over all vertices in a cut set . Internal arcs cancel, leaving the cut identity
Thus every cut bounds every feasible flow. The subtraction of incoming flow is essential; a cut capacity counts only outgoing capacities, but the actual net crossing can include incoming traffic.
If a residual augmenting path exists, augmentation preserves every capacity bound. At an internal path vertex, the change in net outflow is zero, even when one of the residual arcs cancels an original flow. Net source outflow increases by the bottleneck, which is strictly positive. Hence a maximum flow has no such path.
Conversely, suppose no residual path reaches the sink, and let be the set of vertices reachable from the source using positive residual capacity. Every original arc leaving must be saturated, or its forward residual arc would reach another vertex. Every original arc entering must carry zero flow, or its backward residual arc would leave . The cut identity then becomes equality. This gives an equal-valued flow and cut and proves optimality.
For existence, the feasible flows form a nonempty closed bounded subset of a finite-dimensional Euclidean space: the zero flow is feasible and every coordinate lies in its capacity interval. Continuity of the value gives a maximum. Applying the preceding argument to a maximum produces an equal cut, completing the existence proof without assuming algorithmic termination.
When capacities are integers, start from zero and repeatedly augment on any available path. Residual capacities and bottlenecks remain integers, so each augmentation increases the value by at least one. The value is bounded above by the finite sum of outgoing source capacities. Therefore the process terminates, and the resulting integer flow has a matching cut.
Proof X-ray
Two residual facts close the gap
The proof has four separate jobs. The cut identity gives the upper bound for every flow and every cut; augmentation shows that a maximum flow has no augmenting path; the reachability cut shows the converse; compactness and integer steps give existence and integrality.
Key move: take to be everything reachable in the residual network. Absence of forward residual capacity out of says the outward arcs are saturated, and absence of backward residual capacity out of says the inward arcs are empty. These are exactly the two terms that make the cut inequality strict.
What would break without backward arcs: in the first worked example, after the route , forward-only reachability gives . Its outward arcs and are saturated, but the inward arc carries one unit, so the flow value is strictly less than the cut capacity . Nothing is certified, and indeed the flow is not maximum.
Where finiteness enters: existence uses finitely many arcs and finite capacities to make the feasible set compact; integrality uses a finite upper bound and increments of at least one. Neither depends on which augmenting path an algorithm chooses.
The shortest-path certificate needs only one telescoping sum.
Proof
(Telescope the potential inequalities)
For shortest paths, sum the potential inequalities along a walk. All intermediate potential terms telescope, leaving . If every arc of a selected path is tight, the inequality is equality.
This argument does not require nonnegative arc lengths. Nonnegativity becomes necessary for the usual correctness proof of Dijkstra's particular greedy algorithm. Returning to flows, the cut identity also has an algebraic reading.
Concept lensAlgebraic
The cut certificate is a sum of nonnegative errors
For any feasible flow and cut, subtract the net-flow identity from the cut capacity. The gap is the sum of unused capacity on outgoing arcs plus existing flow on incoming arcs. Each term is nonnegative. A residual-reachability cut makes both kinds of error zero: outward arcs are saturated and inward arcs carry no flow. This is the same certificate pattern as the linear-programming duality gap. The graph proof finds a cut where all error terms vanish, while the algebra explains why checking those local facts proves a global maximum.
Finding distance labels
Dijkstra's method initializes the source label to zero and all other labels to infinity. Repeatedly settle an unsettled vertex with least tentative label and relax each outgoing arc: replace the destination label by the smaller of its current label and the settled label plus arc length. Store a predecessor whenever a label improves, so the labels can be converted into actual routes.
Proposition 2.1.4
(Settled labels are exact for nonnegative lengths)
If every arc length is nonnegative, then whenever Dijkstra's method settles a vertex , its label equals the least length of a directed - walk.
Proof
(The first unsettled vertex on a shorter route)
The label of a settled vertex is the length of an actual walk, recorded by predecessors, so it is never below the true distance. Consider a supposedly shorter route to the newly settled vertex and the first unsettled vertex on that route. Its predecessor was already settled, so relaxation gave it a label no larger than the corresponding route prefix. Nonnegativity makes that prefix no larger than the full route length. The least-label selection now contradicts the claimed shorter route.
Infinity labels identify unreachable vertices; they are not ordinary real potential values.
Counterexample mode
One negative arc defeats settle-once labeling
Change to arcs with lengths , , , , and . Dijkstra settles , giving labels and at . It settles and sets to . Since , it settles at before examining . The route actually has length . A negative arc invalidates the nonnegative-prefix argument, even though this graph has no directed cycle. The hypothesis that lengths are nonnegative cannot be dropped; the potential certificate, by contrast, remains valid for negative lengths.
For graphs with negative arcs, the Bellman-Ford recurrence instead tracks the shortest walk using at most arcs. At stage , keep the previous labels and consider every incoming arc from a stage- label. If no negative cycle is reachable, a shortest reachable walk can have its cycles removed without increasing length, so at most arcs suffice. A further improving relaxation detects a reachable negative cycle. This is a different argument from settling vertices permanently.
Worked examples
Worked example 2.1.5
(A backward arc repairs an unfortunate first route)
Take unit capacities on arcs , , , , and . First send one unit along . If only unused forward arcs are examined, neither remaining source route appears able to reach the sink.
The residual network contains , then the backward arc belonging to , then , all with residual capacity one. Augment along this residual path. The flow on decreases from one to zero; the other four original arcs each carry one. The value is now two.
The cut has capacity two, proving optimality. The backward step did not send physical traffic against an unavailable link. It revised an earlier assignment, leaving two ordinary forward routes and .
Worked example 2.1.6
(Compute both sides of a cut certificate)
Let capacities be , , , , and . Send two units along , two along , and one along . The resulting arc flows are in that order.
At , inflow three equals outgoing one plus two; at , inflow two plus one equals outgoing three. Source value is five. The cut has capacity , and the cut containing all vertices except has capacity . Either cut certifies maximality.
For comparison, the cut has outgoing capacity . The arc enters this cut and carries one, so net flow across it is . Counting only outward flow would incorrectly identify six as the flow value.
Worked example 2.1.7
(A route and a distance potential agree)
Use lengths , , , , and . Dijkstra first settles , giving tentative labels two and five at . Settling improves to three and sets to eight. Settling improves to five. The predecessor route is .
The final potential is . The five potential differences are , each no larger than its arc length. The selected three arcs are tight, so the route length five equals the lower bound five.
Common mistakes
Flow conservation is local balance, not the statement that every arc carries the same amount. Branches can split and merge. A feasible flow may also contain a circulation that contributes nothing to source value. A shortest route and a maximum flow therefore require different checks even on the same graph. Distance labels certify a minimum only when every relevant arc inequality holds and a route attains the bound; tentative labels halfway through an algorithm are not automatically a certificate.
Common mistake
(Deleting a saturated arc for good)
Residual capacity is a permitted change to an existing decision. It must be recomputed after augmentation. A saturated forward arc can still have a positive backward residual arc, and a later augmentation can make the forward direction available again. Treating a saturated arc as permanently deleted loses valid improvements.
Common mistake
(Naming a bottleneck without its vertex set)
A set of arcs that looks like a bottleneck is not automatically an - cut. State the vertex set , verify that it contains the source and excludes the sink, and sum all outgoing capacities. An equal-valued feasible flow completes the proof; a cut alone supplies only an upper bound.
Common mistake
(Reading integrality as uniqueness)
Integer capacities guarantee that an integer optimum exists, not that every optimal flow is integer. Take unit-capacity arcs , , , , listed in that order. The integer flows and both have the maximum value . Their average is feasible, also has value , and is therefore an optimal flow with fractional coordinates.
Summary
Residual networks encode reversible changes, and the absence of an augmenting path exposes a saturated cut. Shortest-path potentials encode lower bounds, and tight arcs expose a route attaining that bound. In each case the final evidence consists of feasible objects with matching objective values. Algorithmic assumptions, such as integer capacities or nonnegative lengths, must be distinguished from the broader certificate statements.
Exercises
Quick check
(In the unit-capacity network of the first example, list the original arc flows before and after the residual augmentation, in order . Verify conservation at both internal vertices.)
Solution · Answer
The first assignment is . At , inflow one equals outflow one; the same holds at . The revised assignment is . Now each internal vertex receives one directly from and sends one directly to . The backward residual step subtracts the old flow rather than creating a new original arc.
Quick check
(Replace the capacity of in the second example by one, leaving the other capacities unchanged. Find a maximum flow and a minimum cut.)
Solution · Answer
Use flows , giving value four. Conservation holds because sends one to and one to , while sends its total inflow three to . The cut has outgoing arcs , , and , of total capacity . The sink cut also has capacity four. Feasibility and either matching cut prove optimality.
Quick check
(In the shortest-path example, propose potential . Identify an invalid arc inequality. Give the corrected potential and an attaining path.)
Solution · Answer
On arc , the proposed difference is , greater than length one. On the difference two is allowed, so checking only the last arc misses the failure. The corrected potential is , attained by of length .
Quick check
(For lengths , , , and , explain why source-to-sink walk lengths have no lower bound. Would the conclusion remain valid if the arc were removed and no other arc reached ?)
Solution · Answer
The cycle has length minus one. Starting at , repeat this cycle times, then use . The walk length is , which tends to minus infinity. If removing makes unreachable, there is no source-to-sink walk at all. A reachable negative cycle does not create a route to an unreachable target.
Quick check
(Prove that a feasible potential is also a lower bound for any nonnegative unit flow from to , even if the flow splits across several routes.)
Solution · Answer
Multiply by each nonnegative arc flow and sum. Conservation cancels all internal potential coefficients. Unit net source outflow and unit net sink inflow leave on the left. Thus the total flow cost is at least . This argument also explains the shortest-path linear programming dual without requiring a route decomposition.