Lemma 1 — between two bottleneck occurrences of the reversed arc is used
ProvedEdmondsKarp.ShortestPath.bottleneck_twice_reversed_betweenConsider a run of the labeling method with fewest-arc augmenting paths . Let and suppose is a bottleneck arc relative to and , and also relative to and . Then
Combined with Lemma 2, this bounds how often a given pair of nodes can supply a bottleneck arc.
import Mathlib import Definitions.Def_EdmondsKarp_ShortestPath_Network import Definitions.Def_EdmondsKarp_ShortestPath_Augmentation import Definitions.Def_EdmondsKarp_ShortestPath_Run
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
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 be a type of vertices that is finite and has decidable equality. The statement takes the following inputs:
- is a network on (the type
Network V). - .
- is a sequence of real-valued functions on pairs of vertices, , one for each . These are presumably flows.
- is a sequence of finite lists of vertices , one for each . These are presumably paths.
- The hypothesis holds. Going by its name, it says that is a run of a shortest-augmenting-path procedure on with horizon . The statement does not say which indices this predicate constrains, or how.
- satisfy
- . They are not required to be distinct.
- The arc is a bottleneck arc for and : .
- The arc is also a bottleneck arc for and : .
Under these hypotheses, the theorem concludes that there is an index with
Here is presumably the set of arcs between consecutive vertices of the list . The conclusion is therefore that the reverse arc is used by some path strictly between steps and . The inequalities are strict at both ends.
Degenerate cases:
- Small horizon: because is required, the statement says nothing when .
- Consecutive steps: when , no satisfies , so the conclusion is false. The theorem then asserts that the hypotheses cannot all hold together: cannot be a bottleneck arc at two consecutive steps and of such a run.
- Equal endpoints: when , the conclusion asks for the loop to appear among the arcs of some . Whether can hold for a loop depends on its definition, which is not shown.
- Empty vertex type: if is empty, there are no vertices to choose, so the statement holds vacuously.
- Indices outside the horizon: and are defined for every . Values with are constrained only as far as constrains them.
- Possible vacuity: if or 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.