Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2 — using (u,v)(u,v)(u,v) and later (v,u)(v,u)(v,u) raises δ(s,t)\delta(s,t)δ(s,t) by at least 2

Proved
EdmondsKarp.ShortestPath.resDist_add_two_of_reversed

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

network-flowsp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1shortest-paths

Consider a run f0,…,fKf^0, \dots, f^Kf0,…,fK of the labeling method with fewest-arc augmenting paths P0,…,PK−1P^0, \dots, P^{K-1}P0,…,PK−1, and let δk(s,t)\delta^k(s,t)δk(s,t) be the distance from sss to ttt in the residual network of fkf^kfk. If k<l<Kk < l < Kk<l<K, (u,v)∈Pk(u,v) \in P^k(u,v)∈Pk and (v,u)∈Pl(v,u) \in P^l(v,u)∈Pl, then

δl(s,t)≥δk(s,t)+2.\delta^l(s,t) \ge \delta^k(s,t) + 2.δl(s,t)≥δk(s,t)+2.

Since δ(s,t)\delta(s,t)δ(s,t) never exceeds n−1n-1n−1 while finite, this lemma limits how often a pair of nodes can alternate in augmenting paths.

Formalization Note The inequality is in ℕ∞, with ∞+2=∞\infty + 2 = \infty∞+2=∞.

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

/-- Lemma 2 (p. 251): if `k < l`, `(u, v) ∈ P^k` and `(v, u) ∈ P^l`, then
`δ^l(s, t) ≥ δ^k(s, t) + 2`. -/
theorem resDist_add_two_of_reversed {V : Type} [Fintype V] [DecidableEq V] (N : Network V)
    (K : ℕ) (f : ℕ → V → V → ℝ) (P : ℕ → List V) (hrun : IsShortestRun N K f P)
    (k l : ℕ) (hkl : k < l) (hl : l < K) (u v : V)
    (huv : (u, v) ∈ pathArcs (P k)) (hvu : (v, u) ∈ pathArcs (P l)) :
    resDist N (f k) N.s N.t + 2 ≤ resDist N (f l) N.s N.t := by sorry

end EdmondsKarp.ShortestPath
Source
Edmonds, Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, J. ACM 19(2), 1972, p. 251, Lemma 2
Read-back

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

Setting. NNN is a network on a finite node type VVV:

  • a source sss and a sink ttt with s≠ts \neq ts=t;
  • a finite loop-free set AAA of ordered pairs with (t,s)∉A(t,s) \notin A(t,s)∈/A;
  • real capacities c>0c > 0c>0 on AAA.

Residual arcs. (u,v)∈Nf(u,v) \in N^f(u,v)∈Nf means that either (u,v)∈A(u,v) \in A(u,v)∈A and f(u,v)<c(u,v)f(u,v) < c(u,v)f(u,v)<c(u,v), or (v,u)∈A(v,u) \in A(v,u)∈A and f(v,u)>0f(v,u) > 0f(v,u)>0.

Paths and distance. A directed path from xxx to yyy in NfN^fNf is a list of pairwise distinct nodes from xxx to yyy whose consecutive pairs (steps) lie in NfN^fNf. δf(x,y)∈N∪{∞}\delta^f(x,y) \in \mathbb{N} \cup \{\infty\}δf(x,y)∈N∪{∞} is the minimum number of steps of such a path, or ∞\infty∞ if there is none.

Augmenting paths. An augmenting path is a directed path from sss to ttt. A shortest one has the minimum number of steps among all augmenting paths.

Augmentation. aug⁡(f,P)\operatorname{aug}(f,P)aug(f,P) is defined as follows:

  • it adds εf(P)\varepsilon_f(P)εf​(P) at (t,s)(t,s)(t,s), where εf(P)\varepsilon_f(P)εf​(P) is the minimum over the steps (u,v)(u,v)(u,v) of:

    • c(u,v)−f(u,v)+f(v,u)c(u,v) - f(u,v) + f(v,u)c(u,v)−f(u,v)+f(v,u) if both (u,v),(v,u)∈A(u,v), (v,u) \in A(u,v),(v,u)∈A;
    • c(u,v)−f(u,v)c(u,v) - f(u,v)c(u,v)−f(u,v) if only (u,v)∈A(u,v) \in A(u,v)∈A;
    • f(v,u)f(v,u)f(v,u) otherwise.

    It is 000 if there are no steps.

  • on (x,y)∈A(x,y) \in A(x,y)∈A it adds inc(x,y)\mathrm{inc}(x,y)inc(x,y) and subtracts dec(x,y)\mathrm{dec}(x,y)dec(x,y):

    • inc(x,y)\mathrm{inc}(x,y)inc(x,y) is nonzero only if (x,y)(x,y)(x,y) is a step. It then equals min⁡(ε, c(x,y)−f(x,y))\min(\varepsilon,\, c(x,y) - f(x,y))min(ε,c(x,y)−f(x,y)) if (y,x)∈A(y,x) \in A(y,x)∈A, and ε\varepsilonε otherwise.
    • dec(x,y)\mathrm{dec}(x,y)dec(x,y) is nonzero only if (y,x)(y,x)(y,x) is a step. It then equals max⁡(0, ε−c(y,x)+f(y,x))\max(0,\, \varepsilon - c(y,x) + f(y,x))max(0,ε−c(y,x)+f(y,x)) if (y,x)∈A(y,x) \in A(y,x)∈A, and ε\varepsilonε otherwise.
  • it leaves all other values unchanged.

Run. The hypothesis is a run of length KKK:

  • f0f^0f0 is a flow (≥0\ge 0≥0 on A∪{(t,s)}A \cup \{(t,s)\}A∪{(t,s)}, ≤c\le c≤c on AAA, conservation at every node);
  • for each k<Kk < Kk<K, PkP^kPk is a shortest augmenting path relative to fkf^kfk, and fk+1=aug⁡(fk,Pk)f^{k+1} = \operatorname{aug}(f^k, P^k)fk+1=aug(fk,Pk).

Theorem. For every such run, all indices k<l<Kk < l < Kk<l<K and all nodes u,vu, vu,v: if (u,v)(u,v)(u,v) is a step of PkP^kPk and (v,u)(v,u)(v,u) is a step of PlP^lPl, then

δfk(s,t)+2≤δfl(s,t)in N∪{∞}.\delta^{f^k}(s,t) + 2 \le \delta^{f^l}(s,t) \quad \text{in } \mathbb{N} \cup \{\infty\}.δfk(s,t)+2≤δfl(s,t)in N∪{∞}.

Degenerate cases. The statement is vacuous unless K≥2K \ge 2K≥2.

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