TOPICS
Search

Perfect Matching

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A perfect matching of a finite graph on n vertices 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.

Special classes of graphs obtained by removing a perfect matching are summarized in the following table.

base graph Gderived graph G-M
complete graph K_(2n)cocktail party graph K_(n×2)
complete bipartite graph K_(n,n)crown graph K_(n,n)-M
complete tripartite graph K_(2n,2n,2n)complete tripartite graph minus perfect matching K_(2n,2n,2n)-M
PerfectMatching

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 graph with no perfect matching).

A graph G has a perfect matching iff its matching number nu(G) satisfies

|G|=2nu(G),

where |G|=n is the vertex count of G.

The numbers of unlabeled simple graphs on n=2, 4, 6, ... vertices having a perfect matching are 1, 6, 101, 10413, ... (OEIS A218462), and the corresponding numbers of connected unlabeled simple graphs are 1, 5, 95, 10297, ... (OEIS A218463).

NoPerfectMatchingGraph

The graph illustrated above is a 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."

The Lovász-Plummer conjecture, proved by Esperet et al. (2011), strengthens the bridgeless cubic graph case to an exponential count. Every such graph on n vertices has at least 2^(n/3656) perfect matchings.

Tutte's theorem states that a graph G=(V,E) (where V is the vertex set and E is the edge set) has no perfect matching iff there is a set S subset= V whose removal results in more odd-sized components than |S| (the cardinality of S; Tutte 1947, Pemmaraju and Skiena 2003, p. 344).

See also

Biwheel Conjecture, Biwheel Graph, Brace Graph, Hall's Condition, k-Factor, Lovász-Plummer Conjecture, Marriage Theorem, Matching, Matching Polynomial, Maximal Independent Edge Set, Maximum Independent Edge Set, Near-Perfect Matching, Perfect Matching Polytope, Petersen's Theorem, Tutte's Theorem

Explore with Wolfram|Alpha

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.Esperet, L.; Kardoš, F.; King, A. D.; Král', D.; and Norine, S. "Exponentially Many Perfect Matchings in Cubic Graphs." Adv. Math. 227, 1646-1664, 2011. https://doi.org/10.1016/j.aim.2011.03.015.Faudree, R.; Flandrin, E.; and Ryjáček, Z. "Claw-Free Graphs--A Survey." Disc. Math. 164, 87-147, 1997.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.House of Graphs. "No Perfect Matching Graph." https://houseofgraphs.org/graphs/1243.Johnston, D.; Mark Kayll, P.; and Palmer, C. "Deranged Matchings: Proofs and Conjectures." 30 Oct 2022. https://arxiv.org/abs/2209.11319.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 in "The On-Line Encyclopedia of Integer Sequences."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.

Referenced on Wolfram|Alpha

Perfect Matching

Cite this as:

Weisstein, Eric W. "Perfect Matching." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PerfectMatching.html

Subject classifications