TOPICS
Search

Petersen's Theorem

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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."

CubicGraphWithNoPerfectMatching

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[{"Cubic", {16, 14}}].

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

See also

Bridge, Cubic Graph, Perfect Matching, Tutte's Theorem

Explore with Wolfram|Alpha

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.

Cite this as:

Weisstein, Eric W. "Petersen's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PetersensTheorem.html

Subject classifications