Condição de casamento: o Teorema de Hall
Para esta seção, fixemos $G=(V,E)$ como sendo um grafo bipartido com as partições $\{A,B\}$.E denotemos os vértices da partição $A$ como $a,a', \dots$, bem como os vértices de $B$ como $b,b',\dots$
Um subgrafo gerador $k-$regular é chamado de $k-$fator. Assim, um subgrafo $H \subseteq G$ é $1$-fator de $G$ se, e somente se, $E(H)$ é um emparelhamento de $V$. Surge então o problema de como caracterizar os grafos que possuem um $1$-fator, ou seja, um emparelhamento de todo o seu conjunto de vértices. A busca de algumas condições necessárias e suficientes para a existêcia de um $1$-fator, é um dos principais temas na área do emparelhamento.
Em nosso caso atual de um grafo bipartido, podemos também perguntar de forma mais ´geral quando $G$ contém um emparelhamento de $A$; isso definirá um $1$-fator de $G$ se $|A|=|B|$, uma condição que deve ser mantida de qualquer maneira se $G$ tiver um $1$-fator.
Uma vez que os vértices de partes iguais em um grafo bipartido $G$ não são adjacentes, observa-se que um emparelhamento descreve uma função entre subconjuntos das partes de $G$. Mais precisamente, se $A$ e $B$ denotam as partes dos vértices de $G$, dado $M$ um emparelhamento, fixe $A'$ a coleção dos vértices de $A$ que são pontas de arestas de $M$. Assim, como duas arestas de um emparelhamento nunca possuem uma mesma extremidade, para cada $a\in A'$ existe um único $v_a\in B$ tal que $av_a \in M$. Pelo mesmo argumento, se $v_a = v_b$, então $a,b\in A'$ são iguais. Ou seja, a aplicação $a \mapsto v_a$ descreve uma função injetora entre os conjuntos $A'$ e $B$. Nesta página, estamos interessados em descobrir quando essa função pode estar definida em todo o conjunto $A$.
Na linguagem da Teoria dos Grafos, então, estamos procurando por um emparelhamento $M$ que cobre os vértices da parte $A$, isto é, tal que todos os vértices de $A$ são pontas de uma (única) aresta de $M$. Em particular, dado $S\subset A$, é necessário que $|S|\leq |N(S)|$, para todo $S \subseteq A$, para que a aplicação descrita no parágrafo acima seja injetora, em que $N(S) = \{v\in B : uv \in E \text{ para algum }u\in S\}$. Esse critério é dito ser uma condição de casamento para a existência de um emparelhamento que cobre os vértices de $A$. Curiosamente, essa condição é também suficiente para emparelhar os elementos de $A$:
Teorema de Hall(1935)
Seja $G = (V,E)$ um grafo bipartido com partes $A$ e $B$. Para que exista um emparelhamento que cubra os vértices de $A$, é necessário e suficiente que $|S|\leq |N(S)|$ para todo $S\subset A$.
Uma vez que já verificamos a necessidade de se satisfazer a condição de casamento para garantir a existência de um emparelhamento que cobre uma das partes, apresentaremos três provas de que esse critério é suficiente, demonstrando o Teorema de Hall. A primeira prova utiliza a técnica dos caminhos alternantes, clássica no estudo de emparelhamentos em grafos bipartidos:
Primeira Demonstração: Considere $M$ um emparelhamento que cobre a maior quantidade possível de vértices de $A$. Supondo que a condição de casamento é satisfeita, verificaremos que todo o conjunto $A$ é coberto. Por um momento, suponha que isso não ocorre, existindo $a\in A$ um vértice que não é extremidade de nenhuma aresta de $M$. Com isso, fixe $A'\subset A$ a coleção dos vértices diferentes de $a$ definidos da seguinte maneira: $a'\in A'$ se, e somente se, existe $P_{a'}$ um caminho alternante começando no vértice $a$ e cuja outra extremidade é $a'\in A$.
Observamos que a última aresta de um caminho alternante que termina em $a'$ corresponde a uma aresta emparelhada incidente em $a'$. Portanto, o conjunto $B' = \{b'\in B : a'b'\in M \text{ para algum }a'\in A'\}$ é precisamente a coleção dos penúltimos vértices de um caminho da forma $P_{a'}$ para algum $a'\in A'$. Em particular, a aplicação descrita no primeiro parágrafo (com base no emparelhamento $M$) verifica que $|A'| = |B'|$. Mas, como $\{a\}\cup A'$ tem um elemento a mais que $A'$, a condição de casamento nos garante a existência de $b\in B\setminus B'$ que é vizinho de algum vértice $v\in \{a\}\cup A'$. Com isso, um dos seguintes casos ocorre:
- Suponha que $a$ e $b$ são vizinhos (caso em que $v=a$, por exemplo), de modo que $ab \in E$. Inclusive, essa aresta não pertence ao emparelhamento, pois os vértice $a$ não é coberto por $M$. O vértice $b$ tampouco: se $ub \in E$ fosse uma aresta de $M$, os vértices $a,b$ e $u$ definiriam, nessa ordem, um caminho alternante começando em $a$ e terminando em $u$, de modo que $b\in B'$, o que é uma contradição. Portanto, $M\cup \{ab\}$ é ainda um emparelhamento de $G$, mas que cobre um vértice a mais de $A$ que o emparelhamento $M$.
- Se $a$ e $b$ não são vizinhos, então $v\in A'$. Assim, por definição existe $P_v$ um caminho alternante começando no vértice $a$ e terminando no vértice $v$. Uma vez que $b\notin B'$, o vértice $b$ não deve pertencer a esse caminho: caso contrário, o truncamento de $P_v$ ao seu sucessor nesse caminho atestaria o pertencimento de $b$ a $B'$. Argumentaremos agora que o vértice $b$ também não pode estar coberto por $M$. Para tanto, observamos que, se existe $a'\in A$ tal que $a'b\in M$, então $a'$ não é vértice de $P_v$, pois, a menos de $a$ (que não é vizinho de $b$ por hipótese), todos os demais vértices desse caminho se encontram emparelhados por arestas do próprio caminho. Com isso, a concatenção de $P_v$ com as arestas $vb$ e $ba'$ descreve um caminho alternante, novamente contradizendo o fato de que $b\notin B'$. Portanto, $P_v$ concatenado com a aresta $vb$ descreve um caminho ampliador. A troca das arestas emparelhadas nesse caminho pelas não emparelhadas, consequentemente, determina um emparelhamento de $G$ que cobre $a$ e os demais vértices de $A$ que eram já cobertos por $M$.
Assim, em qualquer um dos casos acima, encontramos um emparelhamento que cobre o vértice $a$ e os demais vértices de $A$ que já eram cobertos por $M$. Isso, contudo, contradiz a escolha de $M$ como um emparelhamento que cobre a maior quantidade possível de vértices de $A$. Logo, $M$ deve ser um emparelhamento que cobre toda a parte $A$ de $G$, como queríamos.
$\square$
Em linhas gerais, a demonstração acima atesta que, satisfeita a condição de casamento, um emparelhamento que cobre o maior número possível de vértices de $A$ na verdade o cobre por inteiro. De maneira dual, é possível verificar que um subgrafo com o menor número de arestas possível e que cobre $A$ é, se satisfeita a condição de casamento, um emparelhamento:
Segunda Demonstração: Suponha que a condição de casamento se verifica. Além disso, seja $H$ um subgrafo de $G$ que contém todos os vértices da parte $A$ e satisfaz a condição de casamento, mas cujo número de arestas é o menor possível. Em particular, em $H$ todo vértice $a\in A$ tem grau maior ou igual a $1$, pois, pela condição de casamento, $1 = |\{a\}| \leq |\{b\in V(H) : ab\in E(H) \}|$. Porém, suponha que $a\in A$ é um vértice com dois vizinhos $b_1,b_2 \in V(H)$. Consequentemente, pela escolha de $H$, os subgrafos $H - ab_1$ e $H - ab_2$ não satisfazem a condição de casamento. Ou seja, para cada $i=1,2$, existe $A_i\subset A$ um conjunto contendo $a$ de modo que $|A_i|> |B_i|$, em que $B_i = \{v\in B : uv \in E(H - ab_i) \text{ para algum }u\in A_i \}$, ou, de maniera mais curta $B_i := N_{H-ab_1}(A_i)$. Em particular, $b_2 \in B_1$ e $b_1 \in B_2$, de maneira que se verificam as seguintes desigualdades:
- $|\{v\in B : uv \in E(H) \text{ para algum }u\in A_1\cap A_2\setminus \{a\}\}|\leq |B_1 \cap B_2|$; pois $\{v\in B : uv \in E(H) \text{ para algum }u\in A_1\cap A_2\setminus \{a\}\}\subset B_i$ para cada $i=1,2$;
- $|A_i|\geq |B_i|+1$ para cada $i=1,2$; pois $|A_i|>|B_i|$;
- $|A_1 \cup A_2| \leq |B_1 \cup B_2|$, pois $|A_1\cup A_2|\leq |\{v\in B : uv \in E(H) \text{ para algum }u\in A_1\cup A_2\}|$ pela condição de casamento (satisfeita em $H$) e $\{v\in B : uv \in E(H) \text{ para algum }u\in A_1\cup A_2\}\subset B_1\cup B_2$.
Consequentemente, contradizendo o fato de que $H$ satisfaz a condição de casamento,
$$|\{v\in B : uv \in E(H) \text{ para algum }u\in A_1\cap A_2\setminus \{a\}\}| := |N_{H}(A_1 \cap A_2 \setminus \{a\})|$$ $$\Downarrow$$ $$|N_{H}(A_1 \cap A_2 \setminus \{a\})| \leq |B_1 \cap B_2|$$ $$\Downarrow$$ $$|N_{H}(A_1 \cap A_2 \setminus \{a\})| = |B_1|+|B_2|-|B_1 \cup B_2|$$ $$\Downarrow$$ $$|N_{H}(A_1 \cap A_2 \setminus \{a\})| = |B_1|+|B_2|-|N_{H}(A_1 \cup A_2)|$$ $$\Downarrow$$ $$|N_{H}(A_1 \cap A_2 \setminus \{a\})| \leq |A_1|-1 + |A_2| -1 -|A_1 \cup A_2|$$ $$\Downarrow$$ $$|N_{H}(A_1 \cap A_2 \setminus \{a\})| = |A_1 \cap A_2|-2$$ $$\Downarrow$$ $$|N_{H}(A_1 \cap A_2 \setminus \{a\})| = |A_1 \cap A_2 \setminus \{a\}|-1$$
Logo, todo vértice $a$ de $H$ deve possuir, nesse subgrafo, exatamente um vizinho. Além disso, dois vértices distintos $u,v \in A \cap V(H)$ não podem possuir o mesmo vizinho em $H$, pois, pela condição de casamento (mais uma vez), $2 = |\{u,v\}|\leq |\{w \in B : uw \in E(H) \text{ ou } vw\in E(H)\}|$. Em resumo, as arestas de $H$ que cobrem $A$ são arestas de um emparelhamento de $G$.
$\square$
Para a prova a seguir, faremos uma indução no número de vértices da parte $A$:
Terceira Demonstração: Se $G$ satisfaz a condição de casamento e $A$ possui um único vértice $v$ como elemento, tem-se que $1 = \{a\} \leq |N(a)|$. Isto é, existe $b\in B$ um vizinho de $a$, de modo que o emparelhamento $\{ab\}$ cobre todos os vértices da parte $A$. Suponha então que $|A|> 1$ e que o Teorema de Hall se verifica em que grafos bipartidos em que uma das partes tem menos que $|A|$ vértices. Nesse cenário, um dos seguintes casos ocorre:
$1.$ Suponha que, para todo subconjunto próprio não vazio $S\subset A$, a condição de casamento é satisfeita “com folga”, isto é, que $|N(S)|\geq |S|+1$. Com isso, fixada $ab \in E$ é uma aresta qualquer, defina o grafo $G' = G[V\setminus \{a,b\}]$. Então, dado $S\subset A\setminus \{a\}$ um subconjunto qualquer, tem-se por hipótese que $|S|\leq |N(S)|-1$. Por sua vez, $N(S)\subset \{v\in B : uv \in E(G')\text{ para algum }u\in S \}\cup \{b\}$, de onde concluímos que
$$|\{v\in B : uv \in E(G')\text{ para algum }u\in S \}| := |N_{G'}(S)| \geq |N(S)|-1 \geq |S|,$$
Ou seja, em $G'$ a condição de casamento é satisfeita, de modo que, por hipótese indutiva, existe $M$ um emparelhamento de $G'$ que cobre os vértices de $A\setminus \{a\}$. Como as arestas de $G'$ não contém o vértice $b$ como extremidade, $M\cup \{ab\}$ é também um emparelhamento de $G$. Como ele cobre todos elementos de $A$, finalizamos o processo indutivo para esse caso.
$2.$ Se o caso acima não ocorre, pela condição de casamento deve existir $A'\subset A$ um subconjunto próprio não vazio tal que $|N(A')| = |A'|$. Denotanto $B' = N(A')$, considere $G' = G[A'\cup B']$. Observamos que em $G'$ a condição de casamento também se verifica, pois, dado $S\subset A'$, tem-se que $|S| \leq |N(S)| \leq |\{v \in B : uv \in E(G')\text{ para algum }u\in S\}|$, visto que $N(S)\subset N(A') = B'$ e que $G'$ é o subgrafo induzido pelos vértices $A'$ e $B'$. Assim, como $A'$ é um subconjunto próprio de $A$, por hipótese indutiva existe $M'$ um emparelhamento de $G'$ que cobre os vértices do conjunto $A'$.
Por outro lado, o subgrafo induzido $G^* = G[V\setminus (A'\cup B')]$ também satisfaz a condição de casamento. Para mostrarmos isso, fixe $S\subset A\setminus A'$ qualquer. Como $|A' \cup S|\leq |N(A' \cup S)|$ pela condição de casamento, $|A'| = |N(A')| = |B'|$ por hipótese e $N(A'\cup S) = B' \cup \{v \in B\setminus B' : uv \in E \text{ para algum }u\in S \} = B' \cup \{v\in B\setminus B' : uv \in E(G^*) \text{ pra algum }u\in S\}$ , devemos ter $|S|\leq |\{v\in B\setminus B' : uv \in E(G^*) \text{ pra algum }u\in S\}|$, verificando a condição de casamento em $G^*$. Ou seja, por hipótese indutiva $G^*$ também admite um emparelhamento $M^*$ que cobre os vértices de $A\setminus A'$. Como $G'$ e $G^*$ não possuem vértices em comum, $M'\cup M^*$ é um emparelhamento em $G$, que cobre os elementos de $A$. Isso finaliza o processo indutivo nesse caso.
$\square$