5.6 (Matching-Duality Theorem), p. 462 — the maximum cardinality of a matching equals the minimum capacity-sum of an odd-set cover
ProvedPathsTreesFlowers.Duality.matching_duality_theoremLet be a finite graph (every edge meets exactly two distinct vertices; parallel edges allowed). Then there exist a maximum-cardinality matching of and a minimum-capacity odd-set cover of with
In words: the maximum cardinality of a matching in equals the minimum capacity-sum of an odd-set cover in , where a single vertex has capacity and covers the edges meeting it, and a set of vertices () has capacity and covers the edges with both end-points in it.
This min–max theorem is the integral linear-programming duality behind maximum matching in general graphs. It generalizes König's theorem for bipartite graphs and is equivalent to the Tutte–Berge formula; an optimal cover is a short certificate that a matching is maximum.
Formalization Note Since everything is finite, a maximum matching and a minimum odd-set cover both exist; the content of the statement is the equality of their sizes.
import Mathlib import Definitions.Def_EdmondsMatching65_Polyhedron_Graph import Definitions.Def_PathsTreesFlowers_Duality_Basic import Definitions.Def_PathsTreesFlowers_Duality_OddSetCover
namespace PathsTreesFlowers.Duality
theorem matching_duality_theorem {V E : Type} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
(G : EdmondsMatching65.Polyhedron.Graph V E) :
∃ M : Finset E, IsMaxMatching G M ∧
∃ S : Finset (Finset V), IsMinOddSetCover G S ∧ M.card = capacitySum S := by sorry
end PathsTreesFlowers.Duality
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.