Perfect matching

Last updated June 11, 2023

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 edge set $E$ , such that every vertex in the vertex set $V$ is adjacent to exactly one edge in $M$ .

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 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 graph on even $n$ vertices and $\lambda _{1}>\lambda _{2}>\ldots >\lambda _{\frac {n}{2}}>0$ be ${\frac {n}{2}}$ 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 _{\frac {n}{2}}$ .^[2] 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, 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.

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 K_n (with n even) is given by the double factorial: $(n-1)!!$ ^[3]

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 ^[4] and computational complexity theory ^[5].

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.

Related Research Articles

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree $k$ is called a $k$ ‑regular graph or regular graph of degree $k$ . Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree.

In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

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.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

In the mathematical discipline of graph theory, the line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$ . $L(G)$ is constructed in the following way: for each edge in $G$ , make a vertex in $L(G)$ ; for every two edges in $G$ that have a vertex in common, make an edge between their corresponding vertices in $L(G)$ .

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In graph theory, a graph is said to be a pseudorandom graph if it obeys certain properties that random graphs obey with high probability. There is no concrete definition of graph pseudorandomness, but there are many reasonable characterizations of pseudorandomness one can consider.

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph $G$ , 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 adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

In graph theory, a mathematical discipline, a factor-critical graph is a graph with $n$ vertices in which every subgraph of $n - 1$ vertices has a perfect matching.

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph $, find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph .$

In the mathematical field of extremal graph theory, homomorphism density with respect to a graph $is a parameter that is associated to each graph in the following manner:$

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices.

In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph.

References

↑ 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 .
↑ Mario Krenn, Xuemei Gu, Anton Zeilinger, Quantum Experiments and Graphs: Multiparty States as Coherent Superpositions of Perfect Matchings, Phys. Rev. Lett. 119, 240403 – Published 15 December 2017
↑ Moshe Y. Vardi, Zhiwei Zhang, Solving Quantum-Inspired Perfect Matching Problems via Tutte's Theorem-Based Hybrid Boolean Constraints, arXiv:2301.09833 [cs.AI], IJCAI'23

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.

[2] 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

[3] Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv: 0906.1317 , Bibcode:2009arXiv0906.1317C .

[4] Mario Krenn, Xuemei Gu, Anton Zeilinger, Quantum Experiments and Graphs: Multiparty States as Coherent Superpositions of Perfect Matchings, Phys. Rev. Lett. 119, 240403 – Published 15 December 2017

[5] Moshe Y. Vardi, Zhiwei Zhang, Solving Quantum-Inspired Perfect Matching Problems via Tutte's Theorem-Based Hybrid Boolean Constraints, arXiv:2301.09833 [cs.AI], IJCAI'23

[1]

[2]

[3]

[4]

[5]