In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G = (V, E), a perfect matching in G is a subset M of E, such that every vertex in V is adjacent to exactly one edge in M.
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.
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 |V | / 2.
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.
Hall's marriage theorem provides a characterization of bipartite graphs which have a perfect matching.
The Tutte theorem provides a characterization for arbitrary graphs.
A spectral characterization for a graph to have a perfect matching is given by Hassani Monfared and Mallik as follows: Let be a graph on even vertices and be distinct nonzero purely imaginary numbers. Then has a perfect matching if and only if there is a real skew-symmetric matrix with graph and eigenvalues . Note that the (simple) graph of a real symmetric or skew-symmetric matrix of order has vertices and edges given by the nonzero off-diagonal entries of .
However, counting the number of perfect matchings, even in bipartite graphs, is #P-complete. This is because computing the permanent of an arbitrary 0–1 matrix (another #P-complete problem) is the same as computing the number of perfect matchings in the bipartite graph having the given matrix as its biadjacency matrix.
Perfect matching polytope
The perfect matching polytope of a graph is a polytope in R|E| in which each corner is an incidence vector of a perfect matching.
- Envy-free matching
- Maximum-cardinality matching
- Perfect matching in high-degree hypergraphs
- Hall-type theorems for hypergraphs
- Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.
- Keivan Hassani Monfared and Sudipta Mallik, Theorem 3.6, Spectral characterization of matchings in graphs, Linear Algebra and its Applications 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004
- Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C.