Tutte's theorem on perfect matchings
ProvedFamousTheorems.tutte_theoremTutte's theorem. A finite simple graph has a perfect matching if and only if for every set of vertices, the graph has at most connected components of odd size.
It is the fundamental characterisation of graphs with perfect matchings, generalising Hall's marriage theorem from bipartite to arbitrary graphs. The Tutte–Berge formula for the maximum matching size and Edmonds' blossom algorithm both grow out of it.
Formalization note. Mathlib's SimpleGraph.tutte; G.IsTutteViolator u says that has more odd components than .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem tutte_theorem {V : Type*} {G : SimpleGraph V} [Finite V] :
(∃ M : G.Subgraph, M.IsPerfectMatching) ↔ ∀ u : Set V, ¬ G.IsTutteViolator u := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `SimpleGraph.tutte`. Proof here reduces to that Mathlib result.