In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a perfect matching in a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
is a
matching that covers every
vertex of the graph. More formally, given a graph , a perfect matching in is a
subset of edge set , such that every vertex in the vertex set is adjacent to exactly one edge in .
A perfect matching is also called a 1-factor; see
Graph factorization
In graph theory, a factor of a graph ''G'' is a spanning subgraph, i.e., a subgraph that has the same vertex set as ''G''. A ''k''-factor of a graph is a spanning ''k''- regular subgraph, and a ''k''-factorization partitions the edges of the gra ...
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.
Characterizations
Hall's marriage theorem
In mathematics, Hall's marriage theorem, proved by , is a theorem with two equivalent formulations:
* The combinatorial formulation deals with a collection of finite sets. It gives a necessary and sufficient condition for being able to select a di ...
provides a characterization of bipartite graphs which have a perfect matching.
The
Tutte theorem
In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of finite graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary gra ...
provides a characterization for arbitrary graphs.
A perfect matching is a spanning
1-regular subgraph, a.k.a. a
1-factor. In general, a spanning ''k''-regular subgraph is a
''k''-factor.
A spectral characterization for a graph to have a perfect matching is given by Hassani Monfared and Mallik as follows: Let
be a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
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
.
Computation
Deciding whether a graph admits a perfect matching can be done in
polynomial time, using any algorithm for finding a
maximum cardinality matching.
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
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simple ...
.
A remarkable theorem of
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
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
''K
n'' (with ''n'' even) is given by the
double factorial:
[.]
Perfect matching polytope
{{Main, 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.
See also
*
Envy-free matching
*
Maximum-cardinality matching
*
Perfect matching in high-degree hypergraphs
*
Hall-type theorems for hypergraphs
References
Matching (graph theory)