Home > Perfect matching
In mathematics, a perfect matching for a graph is a matching (a subset of edges without common vertices) which touches all vertices exactly once. Some definitions also allow graphs with an odd number of vertices to have a perfect matching. These have exactly one unmatched vertex.
There is a polynomial time algorithm (sometimes called Hungarian algorithm ) which, given a graph G, determines if G has a perfect matching and, if it has, finds a perfect matching.
A related problem is, given a graph G, determine the number of perfect matchings in G. This problem is #P Complete. For bipartite graphs, it can be approximately solved in polynomial time. That is, for any ε>0, there is a probabilistic polynomial time algorithm that determines the number of perfect matchings M with error at most εM, with high probability.
