Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 (Edmonds–Karp) — fewest-arc augmentations reach a maximum flow within 14(n3−n)\tfrac14(n^3-n)41​(n3−n) steps

Proved
EdmondsKarp.ShortestPath.shortest_augmenting_path_bound

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

augmenting-pathsedmonds-karpmaximum-flownetwork-flowsp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let NNN be a network on nnn nodes with source sss, sink ttt, return arc (t,s)(t,s)(t,s) and arbitrary positive real capacities. Run the labeling method so that each flow augmentation is done along an augmenting path having fewest arcs: f0f^0f0 is any flow in NNN, and for k=0,1,…,K−1k = 0, 1, \dots, K-1k=0,1,…,K−1, PkP^kPk is an augmenting path with fewest arcs relative to fkf^kfk and fk+1f^{k+1}fk+1 is obtained from fkf^kfk by augmentation along PkP^kPk. Then

  1. the number of augmentations satisfies
K≤14(n3−n);K \le \tfrac14 (n^3 - n);K≤41​(n3−n);
  1. if there is no augmenting path relative to fKf^KfK (so that the method stops), then fKf^KfK is a maximum flow.

Together, these say that a maximum flow is obtained after no more than 14(n3−n)\tfrac14(n^3-n)41​(n3−n) 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 n≤n3n \le n^3n≤n3. The run starts from an arbitrary flow, which is the setting of the paper's proof (p. 251) and contains the zero-flow start.

Preamble
import Mathlib
import Definitions.Def_EdmondsKarp_ShortestPath_Network
import Definitions.Def_EdmondsKarp_ShortestPath_Augmentation
import Definitions.Def_EdmondsKarp_ShortestPath_Run
Formal statement
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
Source
Edmonds, Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, J. ACM 19(2), 1972, p. 251, Theorem 1
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

The declaration concerns a finite type VVV of nodes with decidable equality. Write n=∣V∣n = |V|n=∣V∣ for the number of elements of VVV. The objects involved are:

  • NNN, a value of type Network V, which is defined in the imported file Def_EdmondsKarp_ShortestPath_Network;
  • a natural number KKK;
  • a sequence of real-valued functions on ordered pairs of nodes, f0,f1,f2,…f_0, f_1, f_2, \dotsf0​,f1​,f2​,…, with fk:V×V→Rf_k : V \times V \to \mathbb{R}fk​:V×V→R for each k∈Nk \in \mathbb{N}k∈N;
  • a sequence of finite lists of nodes P0,P1,P2,…P_0, P_1, P_2, \dotsP0​,P1​,P2​,…, where each PkP_kPk​ is a list of elements of VVV.

Hypothesis. The only hypothesis is IsShortestRun(N,K,f,P)\mathrm{IsShortestRun}(N, K, f, P)IsShortestRun(N,K,f,P), a predicate from the imported file Def_EdmondsKarp_ShortestPath_Run. The predicates IsShortestRun\mathrm{IsShortestRun}IsShortestRun, IsAugPath\mathrm{IsAugPath}IsAugPath and IsMaxFlow\mathrm{IsMaxFlow}IsMaxFlow, 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 f0,…,fKf_0, \dots, f_Kf0​,…,fK​ and P0,…P_0, \dotsP0​,…;
  • whether the run constrains fkf_kfk​ for k>Kk > Kk>K or PkP_kPk​ for k≥Kk \ge Kk≥K;
  • whether f0f_0f0​ 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

4K  ≤  n3−n,4K \;\le\; n^3 - n,4K≤n3−n,

where the subtraction is in the natural numbers. Since n3≥nn^3 \ge nn3≥n for every natural number nnn, this subtraction is never truncated, and the bound equals K≤14(n3−n)K \le \tfrac14(n^3 - n)K≤41​(n3−n) exactly.

(b) An implication about the final function fKf_KfK​. Suppose there is no list QQQ of nodes with IsAugPath(N,fK,Q)\mathrm{IsAugPath}(N, f_K, Q)IsAugPath(N,fK​,Q), that is, no list at all counts as an augmenting path for NNN relative to fKf_KfK​. Then IsMaxFlow(N,fK)\mathrm{IsMaxFlow}(N, f_K)IsMaxFlow(N,fK​) 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 fkf_kfk​ for k≠Kk \ne Kk=K.

Degenerate cases.

  • n=0n = 0n=0 or n=1n = 1n=1. Then n3−n=0n^3 - n = 0n3−n=0, so part (a) forces K=0K = 0K=0. The theorem therefore says that any run satisfying IsShortestRun\mathrm{IsShortestRun}IsShortestRun on a network with at most one node has length 000.
  • Longer runs on tiny networks. If IsShortestRun\mathrm{IsShortestRun}IsShortestRun could be satisfied with K≥1K \ge 1K≥1 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 VVV. 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 VVV.
  • Runs with K=0K = 0K=0. Part (a) holds trivially. Part (b) is then a statement about f0f_0f0​ alone.
  • Unsatisfiable hypothesis. If IsShortestRun(N,K,f,P)\mathrm{IsShortestRun}(N, K, f, P)IsShortestRun(N,K,f,P) can never hold for some NNN and KKK, the theorem says nothing about them.
  • Possibly vacuous part (b). If IsAugPath\mathrm{IsAugPath}IsAugPath 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 fk(u,v)f_k(u,v)fk​(u,v) to be nonnegative, bounded by capacities, or conserved at nodes. Any such requirement would have to come from IsShortestRun\mathrm{IsShortestRun}IsShortestRun, which I could not read.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me