= Perfect matching
{wiki}
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>.
\Image[/permanent-perfect-matching-assignments.png]
{title=Three perfect matchings pair every person vertex with one job vertex along allowed edges}
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> $K_{2,2}$ 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.
Back to article page
