Corollary 2 — is a singleton for every vertex of tenacity
ProvedMVBlossoms.corollary_2alternating-pathsblossomsgraph-theorymatchingmicali-vaziranip2o-gran-per-chapterp2o-plan-paperp2o-v1
Let . For every the set
has exactly one element. This is Statement 2 of Theorem 3 at ; it makes well defined.
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_tenacity import Definitions.Def_MVBlossoms_lm import Definitions.Def_MVBlossoms_tm import Definitions.Def_MVBlossoms_baseSet
Formal statement
namespace MVBlossoms
/-- **Corollary 2.** Vazirani, *A Theory of Alternating Paths and Blossoms from the Perspective of Minimum Length*,
Math. Oper. Res. 49(3) (2024), Corollary 2, p.2030: "For every v ∈ Um, the set B(v) is a
singleton." Here Um = {v ∈ V | tenacity(v) = tm} (p.2029).
**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`. -/
theorem corollary_2 {V : Type} [Fintype V] [DecidableEq V] {G : SimpleGraph V} (M : G.Subgraph)
(hM : M.IsMatching) (hstd : tm M < lm M) :
∀ v : V, tenacity M v = tm M → ∃ b : V, baseSet M v = {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), Corollary 2, p.2030
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.