Lemma 11 — a shortest base-to-vertex path meets a shortest path to the base only at the base
ProvedMVBlossoms.lemma_11alternating-pathsblossomsgraph-theorymatchingmicali-vaziranip2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and . Let be an even level() path and an even level() or odd level() path. Then is the only vertex common to and .
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
- encoding: b = base(v), the unique element of B(v) (Definitions 21, 29) → hypothesis IsBase M v b, i.e. baseSet M v = {b}, for every such b; reason: no junk value for base(v); together with Statement 2 / Corollary 2 it is the printed claim
Preamble
import Mathlib import Definitions.Def_MVBlossoms_IsEvenLevelPath import Definitions.Def_MVBlossoms_tenacity import Definitions.Def_MVBlossoms_lm import Definitions.Def_MVBlossoms_tm import Definitions.Def_MVBlossoms_IsBase import Definitions.Def_MVBlossoms_IsEvenLevelFromPath import Definitions.Def_MVBlossoms_IsOddLevelFromPath
Formal statement
namespace MVBlossoms
/-- **Lemma 11.** Vazirani, *A Theory of Alternating Paths and Blossoms from the Perspective of Minimum Length*,
Math. Oper. Res. 49(3) (2024), Lemma 11, p.2031: "Let v ∈ Um and b = base(v). Let p be an even
level(b) path and q be an even level(b;v) or odd level(b;v) path. Then, q meets p at b only."
**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`. "b = base(v)" is the hypothesis `IsBase M v b`
(`B(v) = {b}`). -/
theorem lemma_11 {V : Type} [Fintype V] [DecidableEq V] {G : SimpleGraph V} (M : G.Subgraph)
(hM : M.IsMatching) (hstd : tm M < lm M)
(v b : V) (hv : tenacity M v = tm M) (hb : IsBase M v b)
{f : V} (p : G.Walk f b) (hp : IsEvenLevelPath M p)
(q : G.Walk b v) (hq : IsEvenLevelFromPath M q ∨ IsOddLevelFromPath M q) :
∀ x : V, x ∈ p.support → x ∈ q.support → x = b := 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 11, p.2031
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.