Theorem 1 (Edmonds–Karp) — fewest-arc augmentations reach a maximum flow within steps
ProvedEdmondsKarp.ShortestPath.shortest_augmenting_path_boundLet be a network on nodes with source , sink , return arc and arbitrary positive real capacities. Run the labeling method so that each flow augmentation is done along an augmenting path having fewest arcs: is any flow in , and for , is an augmenting path with fewest arcs relative to and is obtained from by augmentation along . Then
- the number of augmentations satisfies
- if there is no augmenting path relative to (so that the method stops), then is a maximum flow.
Together, these say that a maximum flow is obtained after no more than augmentations, regardless of whether the capacities are commensurable. The bound depends on the number of nodes only; it is the analysis behind the Edmonds–Karp algorithm (breadth-first search for augmenting paths).
Formalization Note The bound is stated in ℕ as 4 * K ≤ n ^ 3 - n with n = Fintype.card V; the truncated subtraction is harmless because . The run starts from an arbitrary flow, which is the setting of the paper's proof (p. 251) and contains the zero-flow start.
import Mathlib import Definitions.Def_EdmondsKarp_ShortestPath_Network import Definitions.Def_EdmondsKarp_ShortestPath_Augmentation import Definitions.Def_EdmondsKarp_ShortestPath_Run
namespace EdmondsKarp.ShortestPath
/-- Theorem 1 (Edmonds–Karp 1972, p. 251): if, in the labeling method for finding a maximum flow in a
network on `n` nodes, each flow augmentation is done along an augmenting path having fewest arcs, then a
maximum flow will be obtained after no more than `¼(n³ − n)` augmentations. Stated for every run
`f 0, …, f K` from an arbitrary flow `f 0`: (a) `4 K ≤ n³ − n`, and (b) if no augmenting path relative to
`f K` exists (the method stops), `f K` is a maximum flow. -/
theorem shortest_augmenting_path_bound {V : Type} [Fintype V] [DecidableEq V] (N : Network V)
(K : ℕ) (f : ℕ → V → V → ℝ) (P : ℕ → List V) (hrun : IsShortestRun N K f P) :
4 * K ≤ Fintype.card V ^ 3 - Fintype.card V ∧
((¬ ∃ Q : List V, IsAugPath N (f K) Q) → IsMaxFlow N (f K)) := by sorry
end EdmondsKarp.ShortestPath
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
The declaration concerns a finite type of nodes with decidable equality. Write for the number of elements of . The objects involved are:
- , a value of type
Network V, which is defined in the imported fileDef_EdmondsKarp_ShortestPath_Network; - a natural number ;
- a sequence of real-valued functions on ordered pairs of nodes, , with for each ;
- a sequence of finite lists of nodes , where each is a list of elements of .
Hypothesis. The only hypothesis is , a predicate from the imported file Def_EdmondsKarp_ShortestPath_Run. The predicates , and , and the structure Network, are defined in files whose code was not given to me. I cannot unfold them, so this read-back does not say:
- what a network contains (capacities, source, sink, or anything else);
- which conditions a run imposes on and ;
- whether the run constrains for or for ;
- whether is required to be a flow at all;
- what makes a list an augmenting path;
- what "maximum flow" means.
The names suggest meanings, but the statement's content depends entirely on those definitions. The docstring above the theorem is a comment and adds no hypotheses or conclusions.
Conclusion. Under the hypothesis, two things hold together.
(a) The bound
where the subtraction is in the natural numbers. Since for every natural number , this subtraction is never truncated, and the bound equals exactly.
(b) An implication about the final function . Suppose there is no list of nodes with , that is, no list at all counts as an augmenting path for relative to . Then holds. Part (b) is only an implication: it does not claim that the run ever reaches a stage where no augmenting path exists. It also asserts nothing about for .
Degenerate cases.
- or . Then , so part (a) forces . The theorem therefore says that any run satisfying on a network with at most one node has length .
- Longer runs on tiny networks. If could be satisfied with in such a network, the theorem would be false. Since it is stated as proved, it amounts to the claim that no such run exists.
- Empty . Whether a network over an empty node type can exist at all depends on the unseen definition of
Network. For example, it cannot exist if a source and sink node are required. If no network exists, the theorem is vacuous for empty . - Runs with . Part (a) holds trivially. Part (b) is then a statement about alone.
- Unsatisfiable hypothesis. If can never hold for some and , the theorem says nothing about them.
- Possibly vacuous part (b). If is satisfied by some list, such as the empty or a one-element list, for every function, then the premise of (b) is never met and (b) is vacuous. Whether this happens depends on the unseen definitions.
- Assumptions I cannot check. Nothing in the visible code requires the values to be nonnegative, bounded by capacities, or conserved at nodes. Any such requirement would have to come from , which I could not read.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.