Consequências do Teorema de Hall
Embora no Teorema de Hall uma das partes do grafo bipartido $G$ seja privilegiada para ser coberta por um emparelhamento, sob certas hipóteses ele pode ser aplicado para encontrar um emparelhamento que cobre todos os vértices:
Corolário
Seja $G = (V,E)$ um grafo bipartido $k-$regular. Então, $G$ admite um emparelhamento $M$ tal que todo $v\in V$ é ponta de uma aresta de $M$.
Demonstração: Sejam $A$ e $B$ as partes do grafo $G$. Uma vez que todo vértice de $A$ tem grau $k$ e toda aresta de $G$ incide em um elemento de $A$, concluímos que $G$ tem $k|A|$ arestas. Pelo mesmo argumento, $G$ possui $k|B|$ arestas. Isto é, $|A| = |B|$. Assim, um emparelhamento que cobre todos os vértices de $A$ deve cobrir também todos os vértices de $B$, pois a aplicação que descrevemos no primeiro parágrafo é injetora.
Pelo Teorema de Hall, então, basta provarmos que a condição de casamento é satisfeita a respeito da parte $A$. De fato, dado $S\subset A$, temos que o número de arestas que incide em $S$ é $k |S|$. Por definição, todas essas arestas incidem em $N(S)$. Nesse conjunto, por sua vez, incidem $k|N(S)|$ arestas. Logo, $k|S|\leq k|N(S)|$, de onde obtemos que $|S|\leq |N(S)|$ e concluímos que a condição de casamento se verifica.
$\square$
Aplicando simultaneamente o Teorema de Hall e o Teorema de Euler, é possível descrever outros subgrafos geradores em uma certa família de grafos:
Corolário
Todo grafo $k-$regular com $k>0$ par admite um $2-$fator.
Demonstração: Seja $G = (V,E)$ um grafo $k-$regular, em que $k>0$ é um número par. Pelo Teorema de Euler, $G$ admite um circuito euleriano, cujos vértices serão sequencialmente denotados, com eventual repetição, por $(v_1,v_2,\dots,v_n)$. Considere então $H$ o grafo obtido a partir de $G$ da seguinte maneira:
- Para cada vértice $v\in V$, considere duas cópias $v^+$ e $v^-$. Com isso, os vértices de $H$ corresponderão ao conjunto $\{v^+,v^- : v \in V\}$.
- O conjunto de arestas de $H$ é dado por $\{v_i^+v_{i+1}^- : 1 \leq i \leq n-1\}$.
A figura a seguir ilustra a construção dos vértices e arestas de $H$ a partir de vértices e arestas de $G$, em que as setas nas arestas de $G$ indicam o sentido em que elas são utilizadas no circuito euleriano.
Por definição, $H$ é um grafo bipartido com partes $\{v^+ : v\in V\}$ e $\{v^- : v\in V\}$. Além disso, como a sequência $(v_1,v_2,\dots,v_n)$ descreve um circuito euleriano, a definição das arestas de $H$ nos garante que esse é um grafo $\frac{k}{2}-$regular. Logo, pelo Corolário acima, existe $M'$ um emparelhamento para $H$ que cobre todos os seus vértices. Ou seja, para cada $v\in V$, os vértices $v^+$ e $v^-$, além de serem extremidades de uma única aresta de $M'$ cada, são cobertos por arestas distintas desse emparelhamento. Logo, o conjunto de arestas $M = \{v_iv_{i+1} : i \text{ é tal que } v_i^+v_{i+1}^- \in M'\}$ é tal que $(V,M)$ é um $2-$fator de $G$.
$\square$