Proof of Theorem 1 — each pair is a bottleneck at most times
ProvedEdmondsKarp.ShortestPath.bottleneck_count_leLet be a network on nodes and consider a run of the labeling method with fewest-arc augmenting paths . For every pair of nodes , let be the number of indices such that or is a bottleneck arc relative to and . Then
Summing over the pairs gives the bound of Theorem 1, since every augmentation has at least one bottleneck arc.
Formalization Note The count is the cardinality of a filtered Finset.range K; the bound is stated multiplied by to stay in ℕ.
import Mathlib import Definitions.Def_EdmondsKarp_ShortestPath_Network import Definitions.Def_EdmondsKarp_ShortestPath_Augmentation import Definitions.Def_EdmondsKarp_ShortestPath_Run
namespace EdmondsKarp.ShortestPath
open Classical in
/-- Proof of Theorem 1 (p. 252): for every pair of nodes `u, v`, the number of occurrences of `(u, v)`
or `(v, u)` as a bottleneck arc throughout the first `K` augmentations is at most `½(n + 1)`,
where `n` is the number of nodes. -/
theorem bottleneck_count_le {V : Type} [Fintype V] [DecidableEq V] (N : Network V)
(K : ℕ) (f : ℕ → V → V → ℝ) (P : ℕ → List V) (hrun : IsShortestRun N K f P) (u v : V) :
2 * ((Finset.range K).filter (fun k =>
IsBottleneck N (f k) (P k) u v ∨ IsBottleneck N (f k) (P k) v u)).card
≤ Fintype.card V + 1 := by sorry
end EdmondsKarp.ShortestPath
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. is a network on a finite node type with nodes:
- a source and a sink with , so ;
- a finite loop-free set of ordered pairs with ;
- real capacities on .
Residual arcs. means that either and , or and .
The number and bottlenecks. The steps of a list are its consecutive pairs. For a step , is:
- if both ;
- if only ;
- if .
is the minimum over the steps (or if there are none). is a bottleneck relative to and if it is a step of with .
Augmenting paths. An augmenting path is a list of pairwise distinct nodes from to whose steps lie in . A shortest one has the minimum number of steps among all augmenting paths.
Augmentation. is defined as follows:
- it adds at ;
- on it adds and subtracts :
- is nonzero only if is a step. It then equals if , and otherwise.
- is nonzero only if is a step. It then equals if , and otherwise.
- it leaves all other values unchanged.
Run. The hypothesis is a run of length :
- is a flow ( on , on , conservation at every node);
- for each , is a shortest augmenting path relative to , and .
Theorem. For every such run and all nodes , let
Then
Equivalently, , and this bound does not depend on .
Degenerate cases.
- counts indices , not individual occurrences: an index at which both and qualify is counted once.
- For , .
- For , , because the steps of a list of distinct nodes are never loops.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.