A perfect matching is a matching in a graph that covers every vertex exactly once. Its edges have no shared endpoints, and every vertex is an endpoint of one selected edge. It is useful when a collection must be divided into disjoint pairs with no element left over.
In a bipartite graph with equally many vertices on its two sides, a perfect matching can assign every person one allowed job and every job one person. The example under permanent of a matrix has three people and three jobs, with exactly three valid assignments. The blue edges below show those three perfect matchings; a crossing in the drawing is not an extra vertex.
Every selected edge covers two vertices, so a graph with an odd integer number of vertices has no perfect matching. An even integer number is necessary but does not guarantee existence: an isolated vertex cannot be covered. A perfect matching also need not be unique. For example, the complete bipartite graph has two perfect matchings, corresponding to the two ways of assigning two people to two jobs.
Counting all perfect matchings is a different question from finding one. For a zero-one biadjacency matrix of a balanced bipartite graph, the count is its permanent of a matrix. The nonzero determinant criterion for a perfect matching supplies an existence test, but cancellation means that a zero determinant does not rule one out.
A finite graph has a perfect matching if and only if the displayed inequalities hold, where counts the connected components of a graph with an odd integer number of vertices. The theorem is associated with William Thomas Tutte.[ref]
Necessity has a direct counting proof: each such component of must send at least one edge of a perfect matching to , and different components must use different vertices of . The sufficiency direction is the substantive content of the theorem. The criterion is useful because vertex degree and parity estimates can prove existence without constructing the perfect matching, as in the perfect matching theorem for a cubic graph with at most two bridges.
A vertex on one side of a balanced bipartite graph is flexible if every incident edge lies in a perfect matching. The strict Hall marriage theorem inequalities for nonempty proper subsets imply flexibility of every vertex: after forcing an edge, removal of its ends loses at most one neighbour from each remaining set. If a perfect matching exists without the strict condition, choose a minimal nonempty tight set. Its induced balanced graph has the strict condition internally, and each internal matching extends using the original matching outside that set. Thus at least one flexible vertex always exists.
A minimum-weight perfect matching pairs every vertex exactly once while minimizing total edge weight. General weighted perfect matching has polynomial-time algorithms. In the Christofides algorithm, it corrects precisely the odd-degree vertices of a minimum spanning tree. Alternating edges of a cyclic order on an even number of vertices give two perfect matchings; the cheaper one costs at most half that cycle's cost.
A one-factorization partitions every edge of a graph into perfect matchings. Each matching uses every vertex exactly once. A total of synthemes is precisely a one-factorization of the complete graph on six points.
