---
tag: 08J7R35B6Q
kind: statement
role: theorem
name: Tutte's theorem
msc: [05C70]
uses: [01VVP10MWJ, 05ZPH8KF9K]
sources:
  - url: https://en.wikipedia.org/wiki/Tutte's_theorem_on_perfect_matchings
    locator: Tutte's theorem
same_as:
  wikidata: Q510197
  wikipedia: Tutte's theorem on perfect matchings
---

## Statement

Let $G$ be a finite [[graph|0JD5C82QMB]] with vertex set $V$.
For $U \subseteq V$, let $o(G - U)$ be the number of [[connected components|01VVP10MWJ]] of $G - U$ with an odd number of vertices.
Then $G$ has a [[perfect matching|05ZPH8KF9K]] if and only if $o(G - U) \le |U|$ for every $U \subseteq V$.

## Remarks

The condition is necessary. In a perfect matching, each odd component of $G - U$ has a vertex that is matched to a vertex of $U$. These vertices of $U$ are distinct.
For $U = \varnothing$, the condition says that each component of $G$ has an even number of vertices.
The theorem is a special case of the Tutte–Berge formula for the size of a maximum matching.

## History

The theorem is named after William Thomas Tutte.

## Explanations

### L1 human

Delete some vertices, and count the pieces with an odd number of vertices that remain.
Each odd piece needs a partner among the deleted vertices, and Tutte's theorem says this is the only obstruction.