Corolário

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

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. Daí $q(G-S) \leq |S|$, como requerido.

• Assim a quantidade de arestas entre $G$ e $G\setminus S$ é pelo menos 3 $3q(G\setminus S)$ e é no máximo $3|S|$, portanto pelo teorema como temos que $q(G - S) \leq |S|$, temos um emparelhamento perfeito.

$\square$