Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 1 — a bottleneck arc of PkP^kPk is not an arc of Nk+1N^{k+1}Nk+1

Proved
EdmondsKarp.ShortestPath.bottleneck_not_residual_next

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

augmenting-pathsnetwork-flowsp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider a run f0,f1,…,fKf^0, f^1, \dots, f^Kf0,f1,…,fK of the labeling method in a network NNN in which f0f^0f0 is a flow and each fk+1f^{k+1}fk+1 is obtained from fkf^kfk by augmentation along an augmenting path PkP^kPk having fewest arcs. Write NkN^kNk for the residual network of fkf^kfk. For every k<Kk < Kk<K and every pair of nodes (u,v)(u,v)(u,v):

(u,v) is a bottleneck arc relative to Pk and fk  ⟹  (u,v)∉Nk+1.(u,v) \text{ is a bottleneck arc relative to } P^k \text{ and } f^k \implies (u,v) \notin N^{k+1}.(u,v) is a bottleneck arc relative to Pk and fk⟹(u,v)∈/Nk+1.

This proposition, together with Proposition 2, drives Lemma 1: a bottleneck arc disappears from the residual network and can only come back after it has been traversed in the opposite direction.

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 1 (p. 252): if `(u, v)` is a bottleneck arc relative to `P^k` and `f^k`, then
`(u, v) ∉ N^{k+1}`. -/
theorem bottleneck_not_residual_next {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) (hb : IsBottleneck N (f k) (P k) u v) :
    ¬ ResArc N (f (k + 1)) u v := 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 1
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. For a function f:V×V→Rf : V \times V \to \mathbb{R}f:V×V→R, (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.

The number ε\varepsilonε. The steps of a list are its consecutive pairs. For a step (u,v)(u,v)(u,v), ε(u,v)\varepsilon(u,v)ε(u,v) is:

  • 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.

εf(P)\varepsilon_f(P)εf​(P) is the minimum of these over the steps of PPP, or 000 if there are none. The pair (u,v)(u,v)(u,v) is a bottleneck relative to PPP and fff if (u,v)(u,v)(u,v) is a step of PPP and ε(u,v)=εf(P)\varepsilon(u,v) = \varepsilon_f(P)ε(u,v)=εf​(P).

Augmenting paths. 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);
  • 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 nonzero only if (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 nonzero only if (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 that (fk)k∈N(f^k)_{k \in \mathbb{N}}(fk)k∈N​ and (Pk)k∈N(P^k)_{k \in \mathbb{N}}(Pk)k∈N​ form a run of length KKK:

  • f0f^0f0 is a flow, meaning f0≥0f^0 \ge 0f0≥0 on A∪{(t,s)}A \cup \{(t,s)\}A∪{(t,s)}, f0≤cf^0 \le cf0≤c on AAA, and inflow equals outflow 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: if (u,v)(u,v)(u,v) is a bottleneck relative to PkP^kPk and fkf^kfk, then (u,v)∉Nfk+1(u,v) \notin N^{f^{k+1}}(u,v)∈/Nfk+1.

Degenerate cases. For K=0K = 0K=0 there is no k<Kk < Kk<K, and 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