Theorem 8.2.2 — König's theorem
ProvedMatousekLP.Integrality.konigLet be a finite bipartite graph. Then the size of a maximum matching in equals the size of a minimum vertex cover of :
Here a matching is a set of edges in which each vertex is incident to at most one edge, and a vertex cover is a set of vertices meeting every edge.
König's theorem is the prototypical combinatorial min–max theorem obtained from linear programming duality together with total unimodularity; Hall's theorem follows from it.
Formalization Note Both extremes are stated as attained: there exist a matching of maximum size and a vertex cover of minimum size with . No supremum or infimum is used. Vertex covers are Mathlib's SimpleGraph.IsVertexCover.
import Mathlib import Definitions.Def_MatousekLP_Integrality_BipartiteGraph
namespace MatousekLP.Integrality
theorem konig {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
(hG : IsBipartite G) :
∃ M : Finset (Sym2 V), IsMatching G M ∧
(∀ M' : Finset (Sym2 V), IsMatching G M' → M'.card ≤ M.card) ∧
∃ C : Finset V, G.IsVertexCover (C : Set V) ∧
(∀ C' : Finset V, G.IsVertexCover (C' : Set V) → C.card ≤ C'.card) ∧
M.card = C.card := by sorry
end MatousekLP.Integrality
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.
Confirmed by the moderator at approval.