1-factor | complete matching

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 n/2 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.

Hall's condition | k-factor | marriage theorem | matching | matching polynomial | maximal independent edge set | maximum independent edge set | near-perfect matching | Petersen's theorem | Tutte's theorem