===== Consequências do Teorema de Hall =====

Embora no Teorema de Hall uma das partes do [[.defbipartite | grafo bipartido]] $G$ seja privilegiada para ser coberta por um [[.matching | emparelhamento]], sob certas hipóteses ele pode ser aplicado para encontrar um emparelhamento que cobre todos os vértices:

<WRAP round box 100%>
=== Corolário === 
//Seja $G = (V,E)$ um grafo bipartido [[.karegular | $k-$regular]]. Então, $G$ admite um emparelhamento $M$ tal que todo $v\in V$ é ponta de uma aresta de $M$.//
</WRAP>

<WRAP round box 100%>
**//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 [[.teoremahall |Teorema de Hall]], então, basta provarmos que a [[.condicaocasamento | 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. 

<wrap right>$\square$</wrap>
</WRAP>

----

Aplicando simultaneamente o Teorema de Hall e o [[.teoeuler | Teorema de Euler]], é possível descrever outros subgrafos geradores em uma certa família de grafos:

<WRAP round box 100%>
=== Corolário ===
//Todo grafo $k-$regular com $k>0$ par admite um [[.kfator | $2-$fator]].//
</WRAP>

<WRAP round box 100%>
**//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 [[.defeuler | 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.

{{ :grafos:doisfator.png?700 |}}

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$. 

<wrap right>$\square$</wrap>
</WRAP>