perfect matching


Definition: A matching, or subset of edges without common vertices, of a connected graph that touches all vertices exactly once. A graph with an odd number of vertices is allowed one unmatched vertex.

Specialization (... is a kind of me.)
bipartite matching.

Aggregate parent (I am a part of or used in ...)
Christofides algorithm.

Note: The term comes from matching each vertex with exactly one other vertex.

Any perfect matching of a graph with n vertices has n/2 edges.

If a graph has a Hamiltonian cycle, it has two different perfect matchings, since the edges in the cycle could be alternately colored. After Douglas Bass ( 5 Sep 1999.

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 17 December 2004.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Paul E. Black, "perfect matching", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 17 December 2004. (accessed TODAY) Available from: