Editing Perfect matching (section)

{{Short description|Matching which covers every node of the graph}}

In [[graph theory]], a '''perfect matching''' in a [[Graph (discrete mathematics)|graph]] is a [[Matching (graph theory)|matching]] that covers every [[Vertex (graph theory)|vertex]] of the graph. More formally, given a graph {{mvar|G}} with edges {{mvar|E}} and vertices {{mvar|V}}, a perfect matching in {{mvar|G}} is a [[subset]] {{mvar|M}} of {{mvar|E}}, such that every vertex in {{mvar|V}} is adjacent to exactly one edge in {{mvar|M}}.  The [[adjacency matrix]] of a perfect matching is a symmetric [[permutation matrix]].

A perfect matching is also called a '''1-factor'''; see [[Graph factorization]] for an explanation of this term. In some literature, the term '''complete matching''' is used. 

Every perfect matching is a [[Maximum cardinality matching|maximum-cardinality matching]], but the opposite is not true. For example, consider the following graphs:<ref name=":0">Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.</ref>

: [[File:Maximum-matching-labels.svg]]

In graph (b) there is a perfect matching (of size 3) since all 6 vertices are matched; in graphs (a) and (c) there is a maximum-cardinality matching (of size 2) which is not perfect, since some vertices are unmatched.

A perfect matching is also a minimum-size [[edge cover]]. If there is a perfect matching, then both the matching number and the edge cover number equal  {{math|{{abs|''V''}} / 2}}. 

A perfect matching can only occur when the graph has an even number of vertices. A '''near-perfect matching''' is one in which exactly one vertex is unmatched.  This can only occur when the graph has an [[odd number]] of vertices, and such a matching must be maximum. In the above figure, part (c) shows a near-perfect matching. If, for every vertex in a graph, there is a near-perfect matching that omits only that vertex, the graph is also called [[Factor-critical graph|factor-critical]].