Petersen,s Theorem
المؤلف:
Errera, A
المصدر:
"Du colorage des cartes." Mathesis 36
الجزء والصفحة:
...
10-5-2022
2413
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[![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/PetersensTheorem/Inline1.svg" style="height:21px; width:6px" />"Cubic", ![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/PetersensTheorem/Inline2.svg" style="height:21px; width:6px" />16, 14![<span style=]()
}" src="https://mathworld.wolfram.com/images/equations/PetersensTheorem/Inline3.svg" style="height:21px; width:6px" />![<span style=]()
}" 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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
