Definição: Emparelhamento Maximal

Um emparelhamento é chamado de emparelhamento maximal se nenhuma aresta do grafo puder ser adicionada sem que a propriedade de não-adjacência entre as arestas seja destruida.

Definição: Emparelhamento Perfeito

Um emparelhamento máximo é chamado de emparelhamento perfeito se todo vértice do grafo é extremidade de alguma aresta do emparelhamento.

Teorema (Tutte $1947$)

Um grafo $G = (V,E)$ possui emparelhamento perfeito se, e somente se, vale $q(G - S) \leq |S|$, $\forall S \subseteq V(G)$, subgrafo de $G$; onde $q(G-S)$ é o número de componentes conexas impares de $G-S$.

Demonstração: Vamos supor que $G$ não possui emparelhamento perfeito, e vamos mostrar com isso que existe um conjunto $S \subseteq V$ “ruim” que não satisfaz $q(G - S) \leq |S|$, $\forall S$, isto é, que não satisfaz a condição de Tutte.

Podemos assumir, sem perca de generalidade, que $G$ é maximal em relação a arestas, ou seja, um $G$ tal que qualquer aresta adicionada nele o torna um emparelhamento perfeito. De fato, se $G'$ é obtido de $G$ adicionando arestas e $S \subseteq V$ é “ruim” para $G'$, então $S$ também é ruim para $G$, isto é, qualquer componente ímpar de $G'-S$ é a união de componentes de $G-S$, e uma delas deve ser novamente ímpar. Assim, $|S| < q(G'-S) \leq q(G-S)$, qualquer aresta adicionada apenas eliminava componentes conexas pares e criava novas componentes impares.

Qual é a aparência de $G$? Claramente, se $G$ contém um conjunto “ruim” $S$ então, por sua aresta-maximalidade e a implicação direta trivial do teorema,

“Se cada uma das componentes conexas de $G \setminus S$ é completa então cada vértice $s \in S$ é adjacente a todos os vértices de $G \setminus s$.” $(*)$

Mas também, inversamente, se um conjunto $S \subseteq V$ satisfaz $(*)$, então $S$ ou o conjunto vazio deve ser ruim: se $S$ não for ruim, podemos juntar os componentes ímpares de $G-S$ de forma disjunta a $S$ e emparelhar todos os vértices restantes, a menos que $|G|$ é ímpar, caso em que $\emptyset$ é ruim.

Assim basta provar que $G$ tem um conjunto $S$ de vértices que satisfaz $(*)$. Seja $S$, então, o conjunto de vértices adjacentes a todos os outros vértices. Se este conjunto $S$ não satisfaz $(*)$, então algum componente de $G-S$ tem vértices não adjacentes $a,a'$. Sejam $a,b,c$ os três primeiros vértices do menor caminho $a-a'$ neste componente; então $ab,bc \in E$, mas $ac \notin E$. Desde que $b\notin S$,existe um vértice $d \in V$ tal que $bd \notin E$. Pela maximalidade de $G$, existe um emparelhamento $M_1$ de $V$ em $G+ac$, e um emparelhamento $M_2$ de $V$ em $G+bd$.

Seja $P=d \dots v$ um caminho maximal em $G$ começando em $d$ com uma aresta de $M_1$ e contendo alternadamente arestas de $M_1$ e $M_2$. Se a última aresta de $P$ estiver em $M_1$ , então $v=b$, caso contrário poderíamos continuar $P$.

Vamos então definir $C:=P+bd$. Se a última aresta de $P$ está em $M_2$, então pela maximalidade de $P$ a $M_1$-aresta em $v$ deve ser $ac$, então $v \in \{a,c\}$; então seja $C$ o ciclo $dPvbd$ (seguindo a figura abaixo).

Em cada caso, $C$ é um ciclo par com todas as outras arestas em $M_2$, e cuja única aresta fora de $E$ é $bd$. Substituindo em $M_2$ suas arestas em $C$ pelas arestas de $C-M_2$, obtemos um emparelhamento de $V$ contido em $E$, uma contradição. Portanto, segue a prova do teorema.

$\square$