Editing Matching (graph theory) (section)

=== Counting problems ===
{{main|Hosoya index}}
The number of matchings in a graph is known as the [[Hosoya index]] of the graph. It is [[Sharp-P-complete|#P-complete]] to compute this quantity, even for bipartite graphs.<ref>[[Leslie Valiant]], ''The Complexity of Enumeration and Reliability Problems'',  SIAM J. Comput., 8(3), 410–421</ref> It is also #P-complete to count [[Perfect matching|perfect matchings]], even in [[bipartite graph]]s, 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]]. However, there exists a fully polynomial time randomized approximation scheme for counting the number of bipartite matchings.<ref>{{cite journal
| last1        = Bezáková
| first1       = Ivona
| last2        = Štefankovič
| first2       = Daniel
| last3        = Vazirani
| first3       = Vijay V.
| author-link3  = Vijay Vazirani
| last4        = Vigoda
| first4       = Eric
| year         = 2008
| title        = Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
| journal      = [[SIAM Journal on Computing]]
| volume       = 37
| issue        = 5
| pages        = 1429–1454
| doi          = 10.1137/050644033
| citeseerx= 10.1.1.80.687
| s2cid = 755231
}}</ref> A remarkable theorem of [[Pieter Kasteleyn|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]] (''n''&nbsp;&minus;&nbsp;1)!!.<ref>{{citation|title=A combinatorial survey of identities for the double factorial|first=David|last=Callan|arxiv=0906.1317|year=2009|bibcode=2009arXiv0906.1317C}}.</ref> The numbers of matchings in complete graphs, without constraining the matchings to be perfect, are given by the [[Telephone number (mathematics)|telephone number]]s.<ref>{{citation
 | last1 = Tichy | first1 = Robert F.
 | last2 = Wagner | first2 = Stephan
 | doi = 10.1089/cmb.2005.12.1004
 | pmid = 16201918
 | issue = 7
 | journal = [[Journal of Computational Biology]]
 | pages = 1004–1013
 | title = Extremal problems for topological indices in combinatorial chemistry
 | url = http://www.math.tugraz.at/fosp/pdfs/tugraz_main_0052.pdf
 | volume = 12
 | year = 2005}}.</ref>

The number of perfect matchings in a graph is also known as the [[hafnian]] of its [[adjacency matrix]].