Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — between two bottleneck occurrences of (u,v)(u,v)(u,v) the reversed arc (v,u)(v,u)(v,u) is used

Proved
EdmondsKarp.ShortestPath.bottleneck_twice_reversed_between

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,…,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. Let k<m<Kk < m < Kk<m<K and suppose (u,v)(u,v)(u,v) is a bottleneck arc relative to PkP^kPk and fkf^kfk, and also relative to PmP^mPm and fmf^mfm. Then

∃ l with k<l<m such that (v,u)∈Pl.\exists\, l \text{ with } k < l < m \text{ such that } (v,u) \in P^l.∃l with k<l<m such that (v,u)∈Pl.

Combined with Lemma 2, this bounds how often a given pair of nodes can supply a bottleneck arc.

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 1 (p. 251): if `k < m` and `(u, v)` is a bottleneck arc relative to `P^k` and `f^k`, and also
relative to `P^m` and `f^m`, then, for some `l` such that `k < l < m`, `(v, u) ∈ P^l`. -/
theorem bottleneck_twice_reversed_between {V : Type} [Fintype V] [DecidableEq V] (N : Network V)
    (K : ℕ) (f : ℕ → V → V → ℝ) (P : ℕ → List V) (hrun : IsShortestRun N K f P)
    (k m : ℕ) (hkm : k < m) (hmK : m < K) (u v : V)
    (hbk : IsBottleneck N (f k) (P k) u v) (hbm : IsBottleneck N (f m) (P m) u v) :
    ∃ l, k < l ∧ l < m ∧ (v, u) ∈ pathArcs (P l) := 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 1
Read-back

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

This statement uses four notions from imported definition files whose text is not included here: Network, IsShortestRun, IsBottleneck and pathArcs. They are described below by their names and how they are used. What they actually mean can only be checked against those files.

Let VVV be a type of vertices that is finite and has decidable equality. The statement takes the following inputs:

  • NNN is a network on VVV (the type Network V).
  • K∈NK \in \mathbb{N}K∈N.
  • fff is a sequence of real-valued functions on pairs of vertices, fi:V×V→Rf^i : V \times V \to \mathbb{R}fi:V×V→R, one for each i∈Ni \in \mathbb{N}i∈N. These are presumably flows.
  • PPP is a sequence of finite lists of vertices PiP^iPi, one for each i∈Ni \in \mathbb{N}i∈N. These are presumably paths.
  • The hypothesis IsShortestRun(N,K,f,P)\mathrm{IsShortestRun}(N, K, f, P)IsShortestRun(N,K,f,P) holds. Going by its name, it says that (fi,Pi)(f^i, P^i)(fi,Pi) is a run of a shortest-augmenting-path procedure on NNN with horizon KKK. The statement does not say which indices iii this predicate constrains, or how.
  • k,m∈Nk, m \in \mathbb{N}k,m∈N satisfy
k<m<K.k < m < K.k<m<K.
  • u,v∈Vu, v \in Vu,v∈V. They are not required to be distinct.
  • The arc (u,v)(u,v)(u,v) is a bottleneck arc for PkP^kPk and fkf^kfk: IsBottleneck(N,fk,Pk,u,v)\mathrm{IsBottleneck}(N, f^k, P^k, u, v)IsBottleneck(N,fk,Pk,u,v).
  • The arc (u,v)(u,v)(u,v) is also a bottleneck arc for PmP^mPm and fmf^mfm: IsBottleneck(N,fm,Pm,u,v)\mathrm{IsBottleneck}(N, f^m, P^m, u, v)IsBottleneck(N,fm,Pm,u,v).

Under these hypotheses, the theorem concludes that there is an index l∈Nl \in \mathbb{N}l∈N with

k<l<mand(v,u)∈pathArcs(Pl).k < l < m \quad\text{and}\quad (v,u) \in \mathrm{pathArcs}(P^l).k<l<mand(v,u)∈pathArcs(Pl).

Here pathArcs(Pl)\mathrm{pathArcs}(P^l)pathArcs(Pl) is presumably the set of arcs between consecutive vertices of the list PlP^lPl. The conclusion is therefore that the reverse arc (v,u)(v,u)(v,u) is used by some path strictly between steps kkk and mmm. The inequalities are strict at both ends.

Degenerate cases:

  • Small horizon: because k<m<Kk < m < Kk<m<K is required, the statement says nothing when K≤1K \le 1K≤1.
  • Consecutive steps: when m=k+1m = k+1m=k+1, no lll satisfies k<l<mk < l < mk<l<m, so the conclusion is false. The theorem then asserts that the hypotheses cannot all hold together: (u,v)(u,v)(u,v) cannot be a bottleneck arc at two consecutive steps kkk and k+1k+1k+1 of such a run.
  • Equal endpoints: when u=vu = vu=v, the conclusion asks for the loop (u,u)(u,u)(u,u) to appear among the arcs of some PlP^lPl. Whether IsBottleneck\mathrm{IsBottleneck}IsBottleneck can hold for a loop depends on its definition, which is not shown.
  • Empty vertex type: if VVV is empty, there are no vertices u,vu, vu,v to choose, so the statement holds vacuously.
  • Indices outside the horizon: fif^ifi and PiP^iPi are defined for every i∈Ni \in \mathbb{N}i∈N. Values with i≥Ki \ge Ki≥K are constrained only as far as IsShortestRun\mathrm{IsShortestRun}IsShortestRun constrains them.
  • Possible vacuity: if IsShortestRun\mathrm{IsShortestRun}IsShortestRun or IsBottleneck\mathrm{IsBottleneck}IsBottleneck cannot be satisfied for some inputs (for example, empty paths), the statement holds vacuously in those cases. Whether that happens cannot be decided from the code shown.
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