Corolário: Petersen $(1891)$

Todo $3-$regular(grafo cúbico) sem pontes admite emparelhamento perfeito.

Demonstração:

Temos que provar que qualquer grafo cúbico sem pontes $G=(V,E)$ satisfaz a condição de Tutte, ou seja, se encaixa no Teorema do Emparelhamento Perfeito. Vamos fixar $S \subset V$ e $C$ uma componente conexa de tamanho impar de $G-S$.

Como $G$ é um grafo cúbico, os graus (em $G$) dos vértices em $C$ somam um número ímpar(pois são ímpares os vérticesde grau $3$), mas apenas uma parte par dessa soma surge das arestas de $C$. Portanto, $G$ tem um número ímpar de arestas $S-C$ e, portanto, possui pelo menos $3$ dessas arestas (uma vez que $G$ não possui pontes).

O número total de arestas entre $S$ e $G-S$ é, portanto, pelo menos $3q(G-S)$. Mas também é no máximo $3|S|$, porque $G$ é cúbico. Pelo Teorema do Emparelhamento Perfeito temos $q(G-S) \leq |S|$, logo temos um emparelhamento perfeito como requerido.

$\square$