A perfect matching of a graph is a matching (i.e., an independent edge set) in which every vertex
of the graph is incident to exactly one edge of the matching.
A perfect matching is therefore a matching containing
edges (the largest possible), meaning
perfect matchings are only possible on graphs with an even number of vertices. A
perfect matching is sometimes called a complete matching or 1-factor.
The nine perfect matchings of the cubical graph are illustrated above.
Note that rather confusingly, the class of graphs known as perfect graphs are distinct from the class of graphs with perfect matchings.
Precomputed graphs having a perfect matching return True for GraphData[g, "PerfectMatching"] in the Wolfram Language.
While not all graphs have a perfect matching, all graphs do have a maximum independent edge set (i.e., a maximum matching; Skiena 1990, p. 240; Pemmaraju and Skiena 2003, pp. 29 and 343). Furthermore, every perfect matching is a maximum independent edge set. A graph either has the same number of perfect matchings as maximum matchings (for a perfect matching graph) or else no perfect matchings (for a no perfect matching graph).
A graph 
has a perfect matching iff its matching
number 
satisfies
 |
where 
is the vertex count of 
.
The numbers of simple graphs on 
, 4, 6, ... vertices having a perfect matching are 1, 6,
101, 10413, ..., (OEIS A218462), and the corresponding
numbers of connected simple graphs are 1, 5, 95, 10297, ... (OEIS A218463).
The graph illustrated above is 16-node graph with no perfect matching that is implemented in the Wolfram Language as GraphData["NoPerfectMatchingGraph"].
Every connected vertex-transitive graph on an even number of vertices has a perfect matching, and each vertex in a connected vertex-transitive graph on an odd number of vertices is missed by a matching that covers all remaining vertices (Godsil and Royle 2001, p. 43; i.e., it has a near-perfect matching).
Every claw-free connected graph with an even number of vertices has a perfect matching (Sumner 1974, Las Vergnas 1975).
Petersen's theorem states that every cubic graph with no bridges has a perfect matching (Petersen 1891; Skiena 1990, p. 244). In fact, this theorem can be extended to read, "every cubic graph with 0, 1, or 2 bridges has a perfect matching."
A result that partially follows from Tutte's theorem states that a graph 
(where 
is the vertex set and 
is the edge set) has no perfect
matching iff there is a set 
whose removal results in more odd-sized components
than 
(the cardinality of 
;
Tutte 1947; Pemmaraju and Skiena 2003, p. 344).
