Perfect matching

<h2 id="characterizations">Characterizations</h2>
<a href="/facts/Hall%2527s_marriage_theorem/hcMXHhUR">Hall's marriage theorem</a> provides a characterization of bipartite graphs which have a perfect matching.
The <a href="/facts/Tutte_theorem/amNCeM8q">Tutte theorem</a> provides a characterization for arbitrary graphs.
A perfect matching is a spanning <a href="/facts/Regular_graph/j9dSoLE6">1-regular</a> subgraph, a.k.a. a <a href="/facts/1-factor/2hx3n7c3">1-factor</a>. In general, a spanning k-regular subgraph is a <a href="/facts/Factor_(graph_theory)/2hx3n7c3">k-factor</a>.
A spectral characterization for a graph to have a perfect matching is given by Hassani Monfared and Mallik as follows: Let 
 
 
 
 G
 
 
 {\displaystyle G}
 
 be a <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> on even 
 
 
 
 n
 
 
 {\displaystyle n}
 
 vertices and 
 
 
 
 
 λ
 
 1
 
 
 >
 
 λ
 
 2
 
 
 >
 …
 >
 
 λ
 
 
 n
 2
 
 
 
 >
 0
 
 
 {\displaystyle \lambda _{1}>\lambda _{2}>\ldots >\lambda _{\frac {n}{2}}>0}
 
 be 
 
 
 
 
 
 n
 2
 
 
 
 
 {\displaystyle {\frac {n}{2}}}
 
 distinct nonzero <a href="/facts/Imaginary_number/6Xh9W3hq">purely imaginary numbers</a>. Then 
 
 
 
 G
 
 
 {\displaystyle G}
 
 has a perfect matching if and only if there is a real <a href="/facts/Skew-symmetric_matrix/nw5CQeLN">skew-symmetric matrix</a> 
 
 
 
 A
 
 
 {\displaystyle A}
 
 with graph 
 
 
 
 G
 
 
 {\displaystyle G}
 
 and <a href="/facts/Eigenvalues/8TjEoT8u">eigenvalues</a> 
 
 
 
 ±
 
 λ
 
 1
 
 
 ,
 ±
 
 λ
 
 2
 
 
 ,
 …
 ,
 ±
 
 λ
 
 
 n
 2
 
 
 
 
 
 {\displaystyle \pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{\frac {n}{2}}}
 
.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> Note that the (simple) graph of a real symmetric or skew-symmetric matrix 
 
 
 
 A
 
 
 {\displaystyle A}
 
 of order 
 
 
 
 n
 
 
 {\displaystyle n}
 
 has 
 
 
 
 n
 
 
 {\displaystyle n}
 
 vertices and edges given by the nonzero off-diagonal entries of 
 
 
 
 A
 
 
 {\displaystyle A}
 
.

<h2 id="computation">Computation</h2>
Deciding whether a graph admits a perfect matching can be done in <a href="/facts/Polynomial-time/77T62gmf">polynomial time</a>, using any algorithm for finding a <a href="/facts/Maximum_cardinality_matching/oKaChmBt">maximum cardinality matching</a>.
However, counting the number of perfect matchings, even in <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graphs</a>, is <a href="/facts/%25E2%2599%25AFP-complete/M6QgPJY6">#P-complete</a>. This is because computing the <a href="/facts/Permanent_(mathematics)/eJWgdahx">permanent</a> 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 <a href="/facts/Biadjacency_matrix/jYXNhYGs">biadjacency matrix</a>. 
A theorem of <a href="/facts/Pieter_Kasteleyn/qBUkvwR8">Pieter Kasteleyn</a> states that the number of perfect matchings in a <a href="/facts/Planar_graph/plREagr9">planar graph</a> can be computed exactly in polynomial time via the <a href="/facts/FKT_algorithm/GQYHD36K">FKT algorithm</a>.
The number of perfect matchings in a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> Kn (with n even) is given by the <a href="/facts/Double_factorial/VSU8AgzB">double factorial</a>: 
 
 
 
 (
 n
 −
 1
 )
 !
 !
 
 
 {\displaystyle (n-1)!!}
 
<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="connection-to-graph-coloring">Connection to Graph Coloring</h2>
An <a href="/facts/Edge_coloring/AcdpUxCv">edge-colored graph</a> can induce a number of (not necessarily proper) <a href="/facts/Graph_coloring/J6HoBfP0">vertex colorings</a> equal to the number of perfect matchings, as every vertex is covered exactly once in each matching. This property has been investigated in <a href="/facts/Quantum_physics/BRc3Mzgr">quantum physics</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> and <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h2 id="perfect-matching-polytope">Perfect matching polytope</h2>
Main article: <a href="/facts/Matching_polytope/PQfMmLnt">Matching polytope</a>
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.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Envy-free_matching/as5YergB">Envy-free matching</a></li>
<li><a href="/facts/Maximum_cardinality_matching/oKaChmBt">Maximum-cardinality matching</a></li>
<li><a href="/facts/Perfect_matching_in_high-degree_hypergraphs/xrtpRSf6">Perfect matching in high-degree hypergraphs</a></li>
<li><a href="/facts/Hall-type_theorems_for_hypergraphs/SVopGt7z">Hall-type theorems for hypergraphs</a></li>
<li>The unique perfect matching problem<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="https://doi.org/10.1016/j.laa.2016.02.004" target="_blank">https://doi.org/10.1016/j.laa.2016.02.004</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="/wiki/Anton_Zeilinger" target="_blank">/wiki/Anton_Zeilinger</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="/wiki/Moshe_Y._Vardi" target="_blank">/wiki/Moshe_Y._Vardi</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Wang, Xiumei; Shang, Weiping; Yuan, Jinjiang (2015-09-01). "On Graphs with a Unique Perfect Matching". Graphs and Combinatorics. 31 (5): 1765–1777. doi:10.1007/s00373-014-1463-8. ISSN 1435-5914. <a href="https://link.springer.com/article/10.1007/s00373-014-1463-8" target="_blank">https://link.springer.com/article/10.1007/s00373-014-1463-8</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Hoang, Thanh Minh; Mahajan, Meena; Thierauf, Thomas (2006). "On the Bipartite Unique Perfect Matching Problem". In Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 4051. Berlin, Heidelberg: Springer. pp. 453–464. doi:10.1007/11786986_40. ISBN 978-3-540-35905-0. <a href="978-3-540-35905-0" target="_blank">978-3-540-35905-0</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Kozen, Dexter; Vazirani, Umesh V.; Vazirani, Vijay V. (1985). "NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching". In Maheshwari, S. N. (ed.). Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science. Vol. 206. Berlin, Heidelberg: Springer. pp. 496–503. doi:10.1007/3-540-16042-6_28. ISBN 978-3-540-39722-9. <a href="978-3-540-39722-9" target="_blank">978-3-540-39722-9</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

Perfect matching open-in-new

Perfect matching