Editing Perfect matching

{{Short description|Matching which covers every node of the graph}}

In [[graph theory]], a '''perfect matching''' in a [[Graph (discrete mathematics)|graph]] is a [[Matching (graph theory)|matching]] that covers every [[Vertex (graph theory)|vertex]] of the graph. More formally, given a graph {{mvar|G}} with edges {{mvar|E}} and vertices {{mvar|V}}, a perfect matching in {{mvar|G}} is a [[subset]] {{mvar|M}} of {{mvar|E}}, such that every vertex in {{mvar|V}} is adjacent to exactly one edge in {{mvar|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. In some literature, the term '''complete matching''' is used. 

Every perfect matching is a [[Maximum cardinality matching|maximum-cardinality matching]], but the opposite is not true. For example, consider the following graphs:<ref name=":0">Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.</ref>

: [[File:Maximum-matching-labels.svg]]

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  {{math|{{abs|''V''}} / 2}}. 

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 graph|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 [[Regular graph|1-regular]] subgraph, a.k.a. a [[1-factor]]. In general, a spanning ''k''-regular subgraph is a [[Factor (graph theory)|''k''-factor]].

A spectral characterization for a graph to have a perfect matching is given by Hassani Monfared and Mallik as follows:  Let <math>G</math> be a [[Graph_(discrete_mathematics)|graph]] on even <math>n</math> vertices and <math>\lambda_1 > \lambda_2 > \ldots > \lambda_{\frac{n}{2}}>0</math> be <math>\frac{n}{2}</math> distinct nonzero [[imaginary number|purely imaginary numbers]]. Then <math>G</math> has a perfect matching if and only if there is a real [[skew-symmetric matrix]] <math>A</math> with graph <math>G</math> and  [[eigenvalues]] <math>\pm \lambda_1, \pm\lambda_2,\ldots,\pm\lambda_{\frac{n}{2}}</math>.<ref name=":1">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</ref> Note that the (simple) graph of a real symmetric or skew-symmetric matrix <math>A</math> of order <math>n</math> has <math>n</math> vertices and edges given by the nonzero off-diagonal entries of <math>A</math>.

== Computation ==
Deciding whether a graph admits a perfect matching can be done in [[Polynomial-time|polynomial time]], using any algorithm for finding a [[maximum cardinality matching]].

However, counting the number of perfect matchings, even in [[Bipartite graph|bipartite graphs]], is [[♯P-complete|#P-complete]]. This is because computing the [[Permanent (mathematics)|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 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]] ''K<sub>n</sub>'' (with ''n'' even) is given by the [[double factorial]]: <math>(n-1)!!</math><ref name=":2">{{citation|last=Callan|first=David|title=A combinatorial survey of identities for the double factorial|year=2009|arxiv=0906.1317|bibcode=2009arXiv0906.1317C}}.</ref>

== Connection to Graph Coloring ==
An [[Edge coloring|edge-colored graph]] can induce a number of (not necessarily proper) [[Graph coloring|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]]<ref>Mario Krenn, Xuemei Gu, [[Anton Zeilinger]], [https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.119.240403 Quantum Experiments and Graphs: Multiparty States as Coherent Superpositions of Perfect Matchings], Phys. Rev. Lett. 119, 240403 – Published 15 December 2017</ref> and [[computational complexity theory]].<ref>[[Moshe Y. Vardi]], Zhiwei Zhang, [https://arxiv.org/abs/2301.09833 Solving Quantum-Inspired Perfect Matching Problems via Tutte's Theorem-Based Hybrid Boolean Constraints], arXiv:2301.09833 [cs.AI], [[International Joint Conference on Artificial Intelligence|IJCAI'23]]</ref>

== Perfect matching polytope ==
{{Main|Matching polytope}}
The '''perfect matching polytope''' of a graph is a polytope in '''R'''<sup>|E|</sup> in which each corner is an incidence vector of a perfect matching.

== See also ==
*[[Envy-free matching]]
*[[Maximum cardinality matching|Maximum-cardinality matching]]
* [[Perfect matching in high-degree hypergraphs]]
* [[Hall-type theorems for hypergraphs]]
* The unique perfect matching problem<ref>{{Cite journal |last1=Wang |first1=Xiumei |last2=Shang |first2=Weiping |last3=Yuan |first3=Jinjiang |date=2015-09-01 |title=On Graphs with a Unique Perfect Matching |url=https://link.springer.com/article/10.1007/s00373-014-1463-8 |journal=Graphs and Combinatorics |language=en |volume=31 |issue=5 |pages=1765–1777 |doi=10.1007/s00373-014-1463-8 |issn=1435-5914}}</ref><ref>{{Cite book |last1=Hoang |first1=Thanh Minh |last2=Mahajan |first2=Meena | author2-link = Meena Mahajan |last3=Thierauf |first3=Thomas |date=2006 |editor-last=Bugliesi |editor-first=Michele |editor2-last=Preneel |editor2-first=Bart |editor3-last=Sassone |editor3-first=Vladimiro |editor4-last=Wegener |editor4-first=Ingo |chapter=On the Bipartite Unique Perfect Matching Problem |chapter-url=https://link.springer.com/chapter/10.1007/11786986_40 |title=Automata, Languages and Programming |series=Lecture Notes in Computer Science |volume=4051 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=453–464 |doi=10.1007/11786986_40 |isbn=978-3-540-35905-0}}</ref><ref>{{Cite book |last1=Kozen |first1=Dexter |last2=Vazirani |first2=Umesh V. |last3=Vazirani |first3=Vijay V. |date=1985 |editor-last=Maheshwari |editor-first=S. N. |chapter=NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching |chapter-url=https://link.springer.com/chapter/10.1007/3-540-16042-6_28 |title=Foundations of Software Technology and Theoretical Computer Science |series=Lecture Notes in Computer Science |volume=206 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=496–503 |doi=10.1007/3-540-16042-6_28 |isbn=978-3-540-39722-9}}</ref>

== References ==
<references />
[[Category:Matching (graph theory)]]