Editing Perfect matching (section)

== 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>