# 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)\leq|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\geq 3c_{p}(G-X)$. But $G$ is 3-regular, thus $t\leq 3|X|$. This gives $c_{p}(G-X)\leq|X|$. ∎

Title Petersen theorem PetersenTheorem 2013-03-22 14:06:07 2013-03-22 14:06:07 scineram (4030) scineram (4030) 15 scineram (4030) Theorem msc 05C70