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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

ندوة اللغة العربية تشهد إقامة جلسة بحثية تسلط الضوء على دورها في العلوم الشرعية والفكرية

جمعية العميد: اللغة العربية مفتاح فهم القرآن الكريم وأحاديث أهل البيت (عليهم السلام)

العتبة العباسية المقدسة: نسعى لأن تكون اللغة العربية طليعةً لاهتمامنا عبر فعاليات علمية وأدبية مستمرة طوال العام

برعاية العتبة العباسية المقدسة.. جمعية العميد تعقد ندوة علمية احتفاء باليوم العالمي للغة العربية

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength