§5, pp. 127–128 — a sequence {G_i} for M yields ⟨y, z⟩₀ satisfying (6)–(10)
ProvedEdmondsMatching65.Polyhedron.certificate_of_blossomSequenceLet be a finite graph with edge weights and let be a matching. If there exists a sequence satisfying conditions (a)–(k) of Theorem (M) for , and , then there is a dual vector satisfying (6) and (7) and, relative to , the conditions (8), (9) and (10).
This is the translation of §5: the paper builds explicitly by on the node sets absorbed into (11), (12) and (13). It is the "if" direction of Theorem (M) in certificate form.
Formalization Note The graph is given by a finite node type , a finite edge type and, for each edge, the unordered pair of its ends (no loops). Parallel edges are allowed, which covers the contracted graphs of Theorem (M); a simple graph is the special case of an injective end map. Vectors have one real coordinate per edge.
import Mathlib import Definitions.Def_EdmondsMatching65_Polyhedron_Graph import Definitions.Def_EdmondsMatching65_Polyhedron_DualProgram import Definitions.Def_EdmondsMatching65_Polyhedron_BlossomSequence
namespace EdmondsMatching65.Polyhedron
theorem certificate_of_blossomSequence {V E : Type*} [Fintype V] [DecidableEq V]
[Fintype E] [DecidableEq E] (G : Graph V E) (c : E → ℝ) (M : Finset E)
(hM : IsMatching G M) (s : BlossomSequence G c M) :
∃ (y : V → ℝ) (z : Finset V → ℝ), DualFeasible G c y z ∧ CompSlack G c M y z := by sorry
end EdmondsMatching65.Polyhedron
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.