Complementar: Teorema do emparelhamento perfeito
Para lançar um pouco mais de luz sobre as técnicas usadas na teoria do emparelhamento, damos agora uma segunda prova do teorema de Tutte. De fato, provaremos um resultado um pouco mais forte, um resultado que coloca uma estrutura interessante do ponto de vista de um emparelhamento em um “grafo arbitrário”. Se o grafo satisfizer a condição do teorema de Tutte, essa estrutura produzirá imediatamente um $1$-fator, isto é, um emparelhamento perfeito.
Um grafo não vazio $G$ é chamado de “fator-crítico” se $G$ não tem $1$- fator, mas para cada vértice $v \in G$ o grafo $G-v$ tem um $1$-fator. Chamamos um conjunto de vértices $S \subseteq V$ compatível,ou emparelhável, com $\mathcal{C}_{G-S}$ se o grafo (bipartido) $G_{S}$, que surge de $G$ contraindo os componentes $C \in \mathcal{C}_{G-S}$ para vértices únicos e excluindo todas as arestas dentro de $S$, contém um emparelhamento de $S$ (Formalmente, $G_{S}$ é o grafo com conjunto de vértices $S \cup \mathcal{C}_{G-S}$ e conjunto de arestas $\{sC | \exists c \in C : sc \in E \}$(veja a figura abaixo)).
Teorema
Todo grafo $G=(V,E)$ contém um conjunto de vértices $S$ com as duas propriedades a seguir:
$(i)$ $S$ é compatível com $\mathcal{C}_{G-S}$;
$(ii)$ Toda componente de $G-S$ é “fator-critico”.
Dado tal conjunto $S$ qualquer, o grafo $G$ contém um $1$-fator se, e somente se, $|S|=|\mathcal{C}_{G-S}|$.
Para qualquer $G$ dado, a afirmação do teorema de Tutte decorre facilmente deste resultado. De fato, por $(i)$ e $(ii)$ temos $|S| \leq |\mathcal{C}_{G-S}| = q(G-S)$, uma vez que os grafos fator-crítico têm ordem ímpar; assim, a condição de Tutte de $q(G-S) \leq |S|$ implica $|S| = |\mathcal{C}_{G-S}|$, e a existência de um $1$-fator decorre da última declaração do teorema.
Demonstração: Observe primeiro que a última afirmação do teorema decorre imediatamente das afirmações $(i)$ e $(ii)$: se $G$ tem um $1$-fator, temos $q(G-S) \leq |S|$ e, portanto, $|S| = |\mathcal{C}_{G-S}|$ como acima; caso contrário, se $|S| = |\mathcal{C}_{G-S}|$ , então a existência de um $1$-fator segue diretamente de $(i)$ e $(ii)$.
Provamos agora a existência de um conjunto $S$ satisfazendo $(i)$ e $(ii)$, por indução em $|G|$. Para $|G|=0$ podemos tomar $S = \emptyset$. Agora seja $G$ dado por $|G| > 0$, e assuma que a afirmação vale para grafos com menos vértices.
Considere os conjuntos $T \subseteq V$ para os quais a condição de Tutte falha, ou seja, para qual
$$d(T) := d_{G}(T):= q(G-T)-|T|$$
é máximo, e seja $S$ o maior desses conjuntos $T$. Observe que $d(S) \geq d(\emptyset) \geq 0$.
Primeiro mostramos que toda componente $C \in \mathcal{C}_{G-S} =: \mathcal{C}$ é ímpar. Se $|C|$ é par, escolha um vértice $c \in C$ e considere $T := S \cup \{c\}$. Como $C-c$ tem ordem ímpar, ele tem pelo menos um componente ímpar, que também é um componente de $G-T$. Portanto, enquanto $|T| = |S|+1$,
$$q(G-T) \geq q(G-S)+1$$
então, $d(T) \geq d(S)$ contradizendo a escolha de $S$.
Em seguida, provamos a afirmação $(ii)$, de que todo $C \in \mathcal{C}$ é um fator-crítico. Suponha que existam $C \in \mathcal{C}$ e $c \in C$ tais que $C' := C-c$ não tenha $1$-fator. Pela hipótese de indução (e pelo fato de que, como mostrado anteriormente, para $G$ fixo nosso teorema implica o teorema de Tutte) existe um conjunto $S' \subseteq V(C')$ com
$$q(C'-S') > |S'|.$$
Como $|C|$ é ímpar e, portanto, $|C'|$ é par, os números $q(C'-S')$ e $|S'|$ são ambos pares ou ambos ímpares, então eles não podem diferir por exatamente $1$. Podemos, portanto, aguçar a desigualdade acima para:
$$q(C'-S') \geq |S'|+2,$$
nos dando $d_{C'}(S') \geq 2$. Então para $T := S \cup \{c\} \cup S'$, temos
$$d(T) \geq d(S)-1-1 + d_{C'}(S') \geq d(S),$$
onde o primeiro $'-1'$ vem da perda de $C$ como um componente ímpar e o segundo vem da inclusão de $c$ no conjunto $T$. Como antes, isso contradiz a escolha de $S$.
Resta mostrar que $S$ é compatível(emparelhável) com $\mathcal{C}_{G-S}$. Caso contrário, pelo teorema do casamento existe um conjunto $S' \subseteq S$ que envia arestas para menos que $|S'|$ componentes em $\mathcal{C}$. Como os outros componentes em $\mathcal{C}$ também são componentes de $G-(S \setminus S')$, o conjunto $T = S \setminus S'$ satisfaz $d(T) > d(S)$, contrária à escolha de $S$.
$\square$
Vamos considerar mais uma vez o conjunto $S$ do teorema acima, juntamente com qualquer emparelhamento $M$ em $G$. Como antes, escrevemos $\mathcal{C} : = \mathcal{C}_{G-S}$. Vamos denotar por $k_{S}$ o número de arestas em $M$ com pelo menos uma extremidade em $S$, e por $k_{\mathcal{C}}$ o número de arestas em $M$ com ambas as extremidades em $G-S$.
Como cada $C \in \mathcal{C}$ é ímpar, pelo menos um de seus vértices não é incidente com uma aresta do segundo tipo. Portanto, todo emparelhamento $M$ satisfaz
$$k_{S} \leq |S|,$$ e $$k_{C} \leq \frac{1}{2} (|V| - |S| -|\mathcal{C}|). (*)$$
Além disso, $G$ contém um emparelhamento $M_0$ com igualdade em ambos os casos: primeiro escolha $|S|$ arestas entre $S$ e $\bigcup \mathcal{C}$ de acordo com $(i)$, e então use $(ii)$ para encontrar um conjunto adequado de $\frac{1}{2}(|C|-1)$ arestas em cada componente $C \in \mathcal{C}$. Este emparelhamento $M_0$, portanto, possui exatamente
$$|M_0| = |S| + \frac{1}{2}(|V|-|S|-|\mathcal{C}|). (**)$$
arestas.
Agora $(*)$ e $(**)$ juntos implicam que todo emparelhamento $M$ de máxima cardinalidade satisfaz ambas as partes de $(*)$ com igualdade: por $|M| \geq |M_0|$ e $(**)$, $M$ tem pelo menos $|S| + \frac{1}{2}(|V|-|S|-|\mathcal{C}|)$ arestas, o que implica por $(*)$ que nenhuma das desigualdades em $(*)$ pode ser estrita.
Mas a igualdade em $(*)$, por sua vez, implica que $M$ tem a estrutura descrita acima: por $k_{S} = |S|$, todo vértice $s \in S$ é o fim de uma aresta $st \in M$ com $t \in G-S$, e por $k_{\mathcal{C}} = \frac{1}{2}(|V|-|S|-|\mathcal{C}|)$ exatamente $\frac{1}{2}(|C|-1)$ arestas de $M$ estão em $C$, para cada $C \in \mathcal{C}$. Finalmente, uma vez que estas últimas arestas perdem apenas um vértice em cada $C$ , as extremidades $t$ das arestas $st$ acima encontram-se em diferentes componentes $C$ para diferentes $s$.
O teorema aparentemente técnico, portanto, esconde uma riqueza de informações estruturais: ele contém a essência de uma descrição detalhada de todas os emparelhamento de máxima cardinalidade em todos os grafos.
Referências
- Reinhard Diestel. “Graph Theory” .5th Electronic Edition 2016, pp. 45. Acesso em 21/03/2023.