Petersen theorem

Every finite , 3-regular (http://planetmath.org/Valency), 2-edge connected graph has a complete matching.

Proof.

Using the notations from the Tutte theorem, we have to prove that for all $X\subseteq V(G)$ the inequality $c_p(G-X)\le |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 $t\ge 3c_p(G-X)$. But $G$ is 3-regular, thus $t\le 3|X|$. This gives $c_p(G-X)\le |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