Perfect 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  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).

REFERENCES

Andersen, L. D. "Factorizations of Graphs." §VII.5 in CRC Handbook of Combinatorial Designs, 2nd ed. Boca Raton, FL: CRC Press, pp. 740-755, 2007.

Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.

Faudree, R.; Flandrin, E.; and Ryjáček, Z. "Claw-Free Graphs--A Survey." Disc. Math. 164, 87-147, 1997.

Las Vergnas, M. "A Note on Matchings in Graphs." Cahiers du Centre d'Études de Recherche Opér. 17, 257-260, 1975.

Lovász, L. and Plummer, M. D. Matching Theory. Amsterdam, Netherlands: Elsevier, 1986.

Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, 2003.Petersen, J. "Die Theorie der Regulären Graphen." Acta Math. 15, 193-200, 1891.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Sloane, N. J. A. Sequences A218462 and A218463.Sumner, D. P. "Graphs with 1-Factors." Proc. Amer. Math. Soc. 42, 8-12, 1974.

Tutte, W. T. "The Factorization of Linear Graphs." J. London Math. Soc. 22, 107-111, 1947.

Wallis, W. D. One-Factorizations. Dordrecht, Netherlands: Kluwer, 1997.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 107-108 and 136-145, 2000.