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

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.