Petersen's Theorem

Petersen's theorem states that every cubic graph with no bridges has a perfect matching (Petersen 1891; Frink 1926; König 1936; 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 graph above shows the smallest counterexample for 3 bridges, namely a connected cubic graph on 16 vertices having no perfect matchings. This graph is implemented in the Wolfram Language as GraphData[{" src="https://mathworld.wolfram.com/images/equations/PetersensTheorem/Inline1.svg" style="height:21px; width:6px" />"Cubic", {" src="https://mathworld.wolfram.com/images/equations/PetersensTheorem/Inline2.svg" style="height:21px; width:6px" />16, 14}" src="https://mathworld.wolfram.com/images/equations/PetersensTheorem/Inline3.svg" style="height:21px; width:6px" />}" src="https://mathworld.wolfram.com/images/equations/PetersensTheorem/Inline4.svg" style="height:21px; width:6px" />].

Errera (1922) strengthened Petersen's theorem by proving that if all bridges of a connected cubic graph  lie on a single path of , then  has a perfect matching.

---

REFERENCES

Errera, A. "Du colorage des cartes." Mathesis 36, 56-60, 1922.

Frink, O. "A Proof of Petersen's Theorem." Ann. Math. 27, 491-493, 1926.

König, D. Theorie der endlichen und unendlichen Graphen; kombinatorische Topologie der Streckenkomplexe. 1936.

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, p. 244, 1990.

اخر الاخبار

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

العتبة العباسية المقدسة تواصل عقد مجلس عزائها بذكرى وفاة السيدة زينب (عليها السلام)

جمعية العميد تصدر الكتاب الأول من الموسوعة التربوية في نهج البلاغة

قسم صناعة الشبابيك يباشر أعمال إدامة الشباك القديم لمرقد الإمامين العسكريين (عليهما السلام)

صحن مرقد أبي الفضل العباس (عليه السلام) يشهد إقامة مجلس عزاء بذكرى وفاة السيدة زينب (عليها السلام)

المزيد

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

طبيب يكشف أفضل مكمل غذائي لتحسين المزاج ودعم الصحة النفسية

دراسة جديدة تكشف أضرار الأطعمة الجاهزة على القلب ؟

6 أطعمة طبيعية تهدئ الزكام دون أدوية.. تعرف عليهم

ماذا يحدث لأعراض الزكام عند تناول الثوم بانتظام؟

المزيد

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

ابتكار ثوري في بطاريات السيارات الكهربائية.. سعة أعلى 4 مرات

ماذا يحدث لجسمك عند شرب الماء الساخن يوميا؟

7 فوائد "خفية" لشرب شاي الكركديه كل يوم

دراسة تكشف قدرة الحيتان على سماع الأصوات منخفضة وعالية التردد من مسافة بعيدة

المزيد

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

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