Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3 — residual distances from sss and to ttt never decrease

Proved
EdmondsKarp.ShortestPath.resDist_monotone

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 in a network NNN with source sss and sink ttt, in which each augmentation is along an augmenting path having fewest arcs. Let δk(u,v)∈{0,1,2,… }∪{∞}\delta^k(u,v) \in \{0,1,2,\dots\} \cup \{\infty\}δk(u,v)∈{0,1,2,…}∪{∞} be the distance from uuu to vvv in the residual network NkN^kNk of fkf^kfk. For every k<Kk < Kk<K and every node uuu,

δk(s,u)≤δk+1(s,u)(1)\delta^k(s,u) \le \delta^{k+1}(s,u) \qquad (1)δk(s,u)≤δk+1(s,u)(1)

and

δk(u,t)≤δk+1(u,t).(2)\delta^k(u,t) \le \delta^{k+1}(u,t). \qquad (2)δk(u,t)≤δk+1(u,t).(2)

This monotonicity of distances under shortest-path augmentation is the key ingredient of Lemma 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

/-- Proposition 3 (p. 252): for `k = 0, 1, 2, …` and all `u`, `δ^k(s, u) ≤ δ^{k+1}(s, u)` (1) and
`δ^k(u, t) ≤ δ^{k+1}(u, t)` (2). -/
theorem resDist_monotone {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) :
    resDist N (f k) N.s u ≤ resDist N (f (k + 1)) N.s u ∧
      resDist N (f k) u N.t ≤ resDist N (f (k + 1)) u 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. 252, Proposition 3, (1) and (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 starting at xxx and ending at yyy, all of whose consecutive pairs (steps) lie in NfN^fNf. The residual distance is

δf(x,y)=inf⁡{#steps of P:P a directed path from x to y in Nf}∈N∪{∞},\delta^f(x,y) = \inf\{\#\text{steps of } P : P \text{ a directed path from } x \text{ to } y \text{ in } N^f\} \in \mathbb{N} \cup \{\infty\},δf(x,y)=inf{#steps of P:P a directed path from x to y in Nf}∈N∪{∞},

with δf(x,y)=∞\delta^f(x,y) = \inftyδf(x,y)=∞ if there is no such path and δf(x,x)=0\delta^f(x,x) = 0δf(x,x)=0.

Augmenting paths. An augmenting path is a directed path from sss to ttt. 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:

    • 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):

    • 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, every k<Kk < Kk<K and every node uuu:

δfk(s,u)≤δfk+1(s,u)andδfk(u,t)≤δfk+1(u,t),\delta^{f^k}(s,u) \le \delta^{f^{k+1}}(s,u) \quad \text{and} \quad \delta^{f^k}(u,t) \le \delta^{f^{k+1}}(u,t),δfk(s,u)≤δfk+1(s,u)andδfk(u,t)≤δfk+1(u,t),

with the comparison taken in N∪{∞}\mathbb{N} \cup \{\infty\}N∪{∞}.

Degenerate cases.

  • For K=0K = 0K=0 the statement is vacuous.
  • For u=su = su=s the first inequality is 0≤00 \le 00≤0, and for u=tu = tu=t the second is 0≤00 \le 00≤0.
  • If uuu is unreachable after the step, the right-hand side is ∞\infty∞ and the inequality holds trivially.
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