---
tag: 05ZPH8KF9K
kind: definition
name: Perfect matching
msc: [05C70]
defines: 0NHK9MFFW9
uses: [0Z87BHAFTB]
sources:
  - url: https://en.wikipedia.org/wiki/Perfect_matching
    locator: lead section
---

## Definition

Let $G$ be a [[graph|0JD5C82QMB]].
A perfect matching of $G$ is a [[matching|0Z87BHAFTB]] $M$ such that every vertex of $G$ is an end of an edge of $M$.

## Remarks

In a perfect matching, each vertex is an end of exactly one edge of $M$. Thus a finite graph with a perfect matching has an even number of vertices.
[[Hall's theorem for bipartite graphs|0X2GJPNPFN]] characterizes the bipartite graphs with a perfect matching. [[Tutte's theorem|08J7R35B6Q]] does this for all finite graphs.
The [[complete graph|03WKB2H474]] $K_4$ has $3$ perfect matchings.

## Explanations

### L1 human

A perfect matching pairs up all vertices of a graph along edges, with nobody left alone.
For this, the number of vertices must be even.