Glossary

Perfect matching

A perfect matching in a graph is a matching that includes every node in the graph. For the matching to include every node, the underlying graph must contain an even total number of nodes.

For example, the five highlighted red edges in the graph below form a perfect matching on the graph's 10 nodes.

Perfect Matching

It is worth noting that a graph simply containing an even number of nodes does not guarantee the existence of a perfect matching in the graph.

Let pn denote the total number of perfect matchings in the complete graph Kn. To count pn, select any node x, and note that we may connect x to one of 2n1 other nodes, which leaves us with 2n2 nodes to match however we like. This reasoning yields the recurrence relation pn=(2n1)pn1, which when combined with the fact that p1=1 provides the closed formula pn=(2n1)(2n3)(5)(3).

Wikipedia