# 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 3{c}_{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 |