§3, pp. 127–128 — for every weight vector, a matching M and ⟨y, z⟩₀ satisfying (6)–(10)
ProvedEdmondsMatching65.Polyhedron.exists_certificateLet be a finite graph. For every real weight vector there exist a matching of and a dual vector which satisfies the dual inequalities (6) and (7) and, relative to , the conditions (8), (9) and (10).
With weak duality and the equality under (6)–(10), this shows that every linear form is maximized over by a matching vector, which by the reduction of §2 gives Theorem (P).
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
namespace EdmondsMatching65.Polyhedron
theorem exists_certificate {V E : Type*} [Fintype V] [DecidableEq V]
[Fintype E] [DecidableEq E] (G : Graph V E) (c : E → ℝ) :
∃ M : Finset E, IsMatching G 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.