Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2 — new residual arcs are reversals of arcs of PkP^kPk

Proved
EdmondsKarp.ShortestPath.residual_next_sub

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

augmenting-pathsnetwork-flowsp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1residual-network

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 write NkN^kNk for the residual network of fkf^kfk. For every k<Kk < Kk<K and all nodes u,vu, vu,v:

(u,v)∈Nk+1  ⟹  (u,v)∈Nk  or  (v,u)∈Pk,(u,v) \in N^{k+1} \implies (u,v) \in N^k \ \text{ or } \ (v,u) \in P^k,(u,v)∈Nk+1⟹(u,v)∈Nk  or  (v,u)∈Pk,

where (v,u)∈Pk(v,u) \in P^k(v,u)∈Pk means that (v,u)(v,u)(v,u) is one of the consecutive pairs of the node sequence PkP^kPk.

The only arcs an augmentation can add to the residual network are the reversals of arcs of the augmenting path; this is used in Lemma 1 and Proposition 3.

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

/-- Proposition 2 (p. 252): if `(u, v) ∈ N^{k+1}` then `(u, v) ∈ N^k` or `(v, u) ∈ P^k`. -/
theorem residual_next_sub {V : Type} [Fintype V] [DecidableEq V] (N : Network V)
    (K : ℕ) (f : ℕ → V → V → ℝ) (P : ℕ → List V) (hrun : IsShortestRun N K f P)
    (k : ℕ) (hk : k < K) (u v : V) (h : ResArc N (f (k + 1)) u v) :
    ResArc N (f k) u v ∨ (v, u) ∈ pathArcs (P k) := by sorry

end EdmondsKarp.ShortestPath
Source
Edmonds, Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, J. ACM 19(2), 1972, p. 252, Proposition 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 c(u,v)−f(u,v)>0c(u,v) - f(u,v) > 0c(u,v)−f(u,v)>0, or (v,u)∈A(v,u) \in A(v,u)∈A and f(v,u)>0f(v,u) > 0f(v,u)>0.

Steps and augmenting paths. The steps of a list are its consecutive pairs. An augmenting path relative to fff is a list of pairwise distinct nodes from sss to ttt whose steps all lie in NfN^fNf. A shortest augmenting path has no more steps than any other augmenting path.

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 PPP 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) if (u,v)∉A(u,v) \notin A(u,v)∈/A.

    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), where:

    • inc(x,y)\mathrm{inc}(x,y)inc(x,y) is 000 unless (x,y)(x,y)(x,y) is a step of PPP. It then equals min⁡(εf(P), c(x,y)−f(x,y))\min(\varepsilon_f(P),\, c(x,y) - f(x,y))min(εf​(P),c(x,y)−f(x,y)) if (y,x)∈A(y,x) \in A(y,x)∈A, and εf(P)\varepsilon_f(P)εf​(P) otherwise.
    • dec(x,y)\mathrm{dec}(x,y)dec(x,y) is 000 unless (y,x)(y,x)(y,x) is a step of PPP. It then equals max⁡(0, εf(P)−c(y,x)+f(y,x))\max(0,\, \varepsilon_f(P) - c(y,x) + f(y,x))max(0,εf​(P)−c(y,x)+f(y,x)) if (y,x)∈A(y,x) \in A(y,x)∈A, and εf(P)\varepsilon_f(P)εf​(P) 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 over the pairs in A∪{(t,s)}A \cup \{(t,s)\}A∪{(t,s)});
  • 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, every k<Kk < Kk<K and all nodes u,vu, vu,v:

(u,v)∈Nfk+1  ⟹  (u,v)∈Nfk  or  (v,u) is a step of Pk.(u,v) \in N^{f^{k+1}} \implies (u,v) \in N^{f^k} \ \text{ or } \ (v,u) \text{ is a step of } P^k.(u,v)∈Nfk+1⟹(u,v)∈Nfk  or  (v,u) is a step of Pk.

Degenerate cases. For K=0K = 0K=0 the statement is vacuous.

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