Mathlib theorem · Existing formal mathematics
ProofAtlas

Existing in Mathlib · Combinatorics

Tutte’s Perfect-Matching Theorem

A finite graph can pair every vertex with exactly one neighbor if and only if every possible deletion of vertices leaves at most one odd connected component per deleted vertex.

Exact theorem

Exact Mathlib statement

theorem SimpleGraph.tutte {V : Type*} {G : SimpleGraph V} [Finite V] : (∃ M : G.Subgraph, M.IsPerfectMatching) ↔ ∀ u : Set V, ¬ G.IsTutteViolator u

The theorem at a glance

Tutte’s Perfect-Matching Theorem at a glance

A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.

Perfect matchings exist precisely when no vertex deletion leaves too many odd components. Explanatory diagram.
Detailed visual description

The poster makes the universal condition primary, contrasts it with a count-correct violating-set certificate, and then follows the source through odd-component exits, a maximal matching-free supergraph, clique components or near-matchings, and an alternating-cycle contradiction.

Statement structure

Statement and scope

Statement map for Tutte’s Perfect-Matching TheoremA finite simple graph has a perfect matching exactly when deleting any vertex set leaves no more odd components than deleted vertices. Claim boundary: This page indexes Mathlib’s existence criterion for perfect matchings in arbitrary finite simple graphs. IsTutteViolator expands to |u| < q(G-u), where q counts odd-cardinality connected components after deleting u. The theorem quantifies over every vertex subset and proves existence, not uniqueness, a construction, an efficient algorithm, a weighted or infinite extension, or anything about the Tutte polynomial. The pinned upstream declaration is SimpleGraph.tutte. The complete formal statement is available in the Exact Mathlib statement section.Mathematical readingA finite simple graphhas a perfect matchingexactly when deletingany vertex set leaves nomore odd components thandeleted vertices.Claim boundaryThis page indexesMathlib’s existencecriterion for perfectmatchings in arbitraryfinite simple graphs.IsTutteViolator expandsto |u| < q(G-u), where qcounts odd-cardinalityconnected componentsafter deleting u. Thetheorem quantifies overevery vertex subset andproves existence, notuniqueness, aconstruction, anefficient algorithm, aweighted or infiniteextension, or anythingabout the Tuttepolynomial.Pinned declarationmathlib ·SimpleGraph.tutteStatement map for Tutte’s Perfect-Matching TheoremA finite simple graph has a perfect matching exactly when deleting any vertex set leaves no more odd components than deleted vertices. Claim boundary: This page indexes Mathlib’s existence criterion for perfect matchings in arbitrary finite simple graphs. IsTutteViolator expands to |u| < q(G-u), where q counts odd-cardinality connected components after deleting u. The theorem quantifies over every vertex subset and proves existence, not uniqueness, a construction, an efficient algorithm, a weighted or infinite extension, or anything about the Tutte polynomial. The pinned upstream declaration is SimpleGraph.tutte. The complete formal statement is available in the Exact Mathlib statement section.Mathematical readingA finite simple graphhas a perfect matchingexactly when deletingany vertex set leaves nomore odd components thandeleted vertices.Claim boundaryThis page indexesMathlib’s existencecriterion for perfectmatchings in arbitraryfinite simple graphs.IsTutteViolator expandsto |u| < q(G-u), where qcounts odd-cardinalityconnected componentsafter deleting u. Thetheorem quantifies overevery vertex subset andproves existence, notuniqueness, aconstruction, anefficient algorithm, aweighted or infiniteextension, or anythingabout the Tuttepolynomial.Pinned declarationmathlib ·SimpleGraph.tutte

Read the exact Mathlib declaration

This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.

A finite graph has a perfect matching exactly when q(G−U) never exceeds |U|. Explanatory diagram.
Detailed visual description

One finite graph is viewed through a spanning matching and through the universal deletion test. Stroke, shape, and grouping distinguish matched pairs, removed vertices, odd components, and even components without relying on color alone.

Why it matters

A mathematical landmark

Tutte’s theorem is the definitive structural criterion for perfect matchings in general finite graphs. Mathlib formalizes the obstruction as an explicit Tutte-violator predicate and proves both necessity and sufficiency.

ProofAtlas record

What has been checked

Upstream indexedPinned source bytes verified locally
Locally reproducedExact upstream declaration replayed
Reviewed pageCurrent public presentation reviewed
Accepted Atlas resultNot recorded for the preferred artifact

Mathlib is the source of the theorem; the local Lean replay and page review are separate.

Claim boundary

No new theorem is claimed

This page indexes Mathlib’s existence criterion for perfect matchings in arbitrary finite simple graphs. IsTutteViolator expands to |u| < q(G-u), where q counts odd-cardinality connected components after deleting u. The theorem quantifies over every vertex subset and proves existence, not uniqueness, a construction, an efficient algorithm, a weighted or infinite extension, or anything about the Tutte polynomial.

Source and local evidence

Where the theorem comes from

Existing declaration
SimpleGraph.tutte in mathlib
Relationship
The checked artifact is the upstream declaration itself
Local Lean evidence
artifact.library.mathlib.tutte-theorem.v001
Source
Open the pinned upstream reference