More formally, given a graph G with edges E and vertices V, 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. 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.
A perfect matching is also a minimum-size edge cover.
A perfect matching can only occur when the graph has an even number of vertices.
This can only occur when the graph has an odd number of vertices, and such a matching must be maximum.
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
has a perfect matching if and only if there is a real skew-symmetric matrix
[2] Note that the (simple) graph of a real symmetric or skew-symmetric matrix
However, counting the number of perfect matchings, even in bipartite graphs, is #P-complete.
A theorem of Pieter Kasteleyn states that the number of perfect matchings in a planar graph can be computed exactly in polynomial time via the FKT algorithm.
The number of perfect matchings in a complete graph Kn (with n even) is given by the double factorial:
[3] An edge-colored graph can induce a number of (not necessarily proper) vertex colorings equal to the number of perfect matchings, as every vertex is covered exactly once in each matching.
This property has been investigated in quantum physics[4] and computational complexity theory.