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 In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...

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 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 In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum ...

. 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 In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is a multiple of two, and odd if it is not.. For example, −4, 0, 82 are even because \begin -2 \cdot 2 &= -4 \\ 0 \cdot 2 &= 0 \\ 41 ...

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 provides a characterization of bipartite graphs which have a perfect matching. The Tutte theorem 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

G

be a

on even

n

vertices and

\lambda_1 > \lambda_2 > \ldots > \lambda_>0

\frac

distinct nonzero purely imaginary numbers. Then

G

has a perfect matching if and only if there is a real skew-symmetric matrix

A

with graph

G

and eigenvalues

\pm \lambda_1, \pm\lambda_2,\ldots,\pm\lambda_

. Note that the (simple) graph of a real symmetric or skew-symmetric matrix

A

of order

n

has

n

vertices and edges given by the nonzero off-diagonal entries of

A

Computation

Deciding whether a graph admits a perfect matching can be done in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

, using any algorithm for finding a

maximum cardinality matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is ...

. However, counting the number of perfect matchings, even in

bipartite graphs In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

, 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. A remarkable theorem of Kasteleyn states that the number of perfect matchings in a

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

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 ...

''K_n'' (with ''n'' even) is given by the

double factorial In mathematics, the double factorial or semifactorial of a number , denoted by , is the product of all the integers from 1 up to that have the same parity (odd or even) as . That is, :n!! = \prod_^ (n-2k) = n (n-2) (n-4) \cdots. For even , the ...

(n-1)!!

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.

References

Matching (graph theory)

Characterizations

Computation

Perfect matching polytope

See also

References