Proposition 1 — a bottleneck arc of is not an arc of
ProvedEdmondsKarp.ShortestPath.bottleneck_not_residual_nextConsider a run of the labeling method in a network in which is a flow and each is obtained from by augmentation along an augmenting path having fewest arcs. Write for the residual network of . For every and every pair of nodes :
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.
import Mathlib import Definitions.Def_EdmondsKarp_ShortestPath_Network import Definitions.Def_EdmondsKarp_ShortestPath_Augmentation import Definitions.Def_EdmondsKarp_ShortestPath_Run
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. is a network on a finite node type :
- a source and a sink with ;
- a finite loop-free set of ordered pairs with ;
- real capacities on .
Residual arcs. For a function , means that either and , or and .
The number . The steps of a list are its consecutive pairs. For a step , is:
- if both ;
- if only ;
- if .
is the minimum of these over the steps of , or if there are none. The pair is a bottleneck relative to and if is a step of and .
Augmenting paths. An augmenting path relative to is a list of pairwise distinct nodes from to whose steps all lie in . A shortest augmenting path has no more steps than any other augmenting path.
Augmentation. is defined as follows:
- it adds at ;
- on it adds and subtracts , where:
- is nonzero only if is a step of . It then equals if , and otherwise.
- is nonzero only if is a step of . It then equals if , and otherwise.
- it leaves all other values unchanged.
Run. The hypothesis is that and form a run of length :
- is a flow, meaning on , on , and inflow equals outflow at every node over the pairs in ;
- for each , is a shortest augmenting path relative to , and .
Theorem. For every such run, every and all nodes : if is a bottleneck relative to and , then .
Degenerate cases. For there is no , and the statement is vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.