Lemma 5 — a max level path to a vertex of tenacity contains a unique bridge of tenacity
ProvedMVBlossoms.lemma_5alternating-pathsblossomsgraph-theorymatchingmicali-vaziranip2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a vertex with and let be a max level() path. Then exactly one edge of is a bridge of tenacity .
This is Statement 1 of Theorem 3 at , with uniqueness.
Formalization Note Throughout, is a finite simple graph and a matching of ; levels and tenacities take values in . The section's standing assumption (p.2018: "Henceforth, we will assume that ") is a hypothesis.
Differences from the source:
- encoding: levels, tenacities and l_m equal ∞ when no path exists (Definitions 3, 4) → values in ℕ∞, defined as infima (⊤ for an empty family); reason: Lean convention; same instances
Preamble
import Mathlib import Definitions.Def_MVBlossoms_IsMaxLevelPath import Definitions.Def_MVBlossoms_tenacity import Definitions.Def_MVBlossoms_edgeTenacity import Definitions.Def_MVBlossoms_lm import Definitions.Def_MVBlossoms_tm import Definitions.Def_MVBlossoms_IsBridge
Formal statement
namespace MVBlossoms
/-- **Lemma 5.** Vazirani, *A Theory of Alternating Paths and Blossoms from the Perspective of Minimum Length*,
Math. Oper. Res. 49(3) (2024), Lemma 5, p.2028: "Let v be a vertex of tenacity tm and p be a max
level(v) path. Then, p contains a unique bridge of tenacity tm."
**Formalization Note.** `V` is finite (`Fintype`), `G` is a simple graph and `M` a matching (`hM`); levels and
tenacities are in `ℕ∞` (definitions `evenLevel`, `oddLevel`, `tenacity`, `edgeTenacity`). The paper's standing assumption `t_m < l_m` ("Henceforth, we will assume that tm<lm",
p.2018; restated on p.2027) is the hypothesis `hstd`. Edges of `p` are unordered pairs `e : Sym2 V`
(`p.edges`); uniqueness is `∃!` over them. -/
theorem lemma_5 {V : Type} [Fintype V] [DecidableEq V] {G : SimpleGraph V} (M : G.Subgraph)
(hM : M.IsMatching) (hstd : tm M < lm M)
(v : V) (hv : tenacity M v = tm M) {f : V} (p : G.Walk f v) (hp : IsMaxLevelPath M p) :
∃! e : Sym2 V, e ∈ p.edges ∧
∃ a b : V, e = s(a, b) ∧ IsBridge M a b ∧ edgeTenacity M a b = tm M := by sorry
end MVBlossoms
Source
Vazirani, A Theory of Alternating Paths and Blossoms from the Perspective of Minimum Length, Math. Oper. Res. 49(3) (2024), Lemma 5, p.2028
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.