Perfect matching

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph.

Uses your system voice; voice and rate in settings.

≈ 3 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exactly one edge in . The adjacency matrix of a perfect matching is a symmetric permutation matrix.

A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true.

For example, consider the following graphs: In graph (b) there is a perfect matching (of size 3) since all 6 vertices are matched; in graphs (a) and (c) there is a maximum-cardinality matching (of size 2) which is not perfect, since some vertices are unmatched. A perfect matching is also a minimum-size edge cover.

If there is a perfect matching, then both the matching number and the edge cover number equal . A perfect matching can only occur when the graph has an even number of vertices. A near-perfect matching is one in which exactly one vertex is unmatched.

This can only occur when the graph has an odd number of vertices, and such a matching must be maximum. In the above figure, part (c) shows a near-perfect matching. If, for every vertex in a graph, there is a near-perfect matching that omits only that vertex, the graph is also called factor-critical.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1298087773 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001298087773 · captured 2025-06-30 · ledger · version history

Cite this page as: encyclopegia.org, “Perfect matching”, snapshot enwiki-001298087773. https://encyclopegia.org/a/perfect-matching

Sources cited in this revision

6 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.