graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

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

is a matching that covers every vertex of the graph. More formally, given a graph with edges and vertices , a perfect matching in is a

subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), 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 a ...

of , such that every vertex in is adjacent to exactly one edge in . The

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...

of a perfect matching is a symmetric

permutation matrix In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0. An permutation matrix can represent a permutation of elements. ...

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

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:Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5. : 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 In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is divisible by 2, and odd if it is not.. For example, −4, 0, and 82 are even numbers, while −3, 5, 23, and 69 are odd numbers. The ...

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 In mathematics, particularly in linear algebra, a skew-symmetric (or antisymmetric or antimetric) matrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition In terms of the entries of the matrix, if a ...

A

with graph

G

and

eigenvalues In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a ...

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

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

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

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

. A theorem of Pieter Kasteleyn states that the number of perfect matchings in a

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

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

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

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

(n-1)!!

Connection to Graph Coloring

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 Quantum mechanics is the fundamental physical Scientific theory, theory that describes the behavior of matter and of light; its unusual characteristics typically occur at and below the scale of atoms. Reprinted, Addison-Wesley, 1989, It is ...

and

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

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.

References

Matching (graph theory)

Characterizations

Computation

Connection to Graph Coloring

Perfect matching polytope

See also

References