Petersen theorem

Every finite , 3-regular (, 2-edge connected graphMathworldPlanetmath has a complete matching.


Using the notations from the Tutte theoremMathworldPlanetmath, we have to prove that for all XV(G) the inequalityMathworldPlanetmath cp(G-X)|X| holds. There are at least 3 edges running between X and an odd component of G-X: there cannot be one edge, since G is 2-edge connected, and there also cannot be two edges, because three edges start from all vertices of an odd component, so the number of edges leaving an odd component is odd. Let t be the number of all edges between X and the odd components of G-X. Now we have t3cp(G-X). But G is 3-regular, thus t3|X|. This gives cp(G-X)|X|. ∎

Title Petersen theorem
Canonical name PetersenTheorem
Date of creation 2013-03-22 14:06:07
Last modified on 2013-03-22 14:06:07
Owner scineram (4030)
Last modified by scineram (4030)
Numerical id 15
Author scineram (4030)
Entry type Theorem
Classification msc 05C70