===== Condição de Casamento =====

<WRAP round box 100%>
Se $G = (V,E)$ é um grafo [[.defbipartite | bipartido]] com partes $A$ e $B$, observa-se que, para que exista um [[.matching | emparelhamento]] $M$ tal que todos os vértices de $A$ sejam pontas de uma aresta de $M$ (ou, em outras palavras, para que $M$ cubra $A$), devemos ter $|S|\leq |N(S)|$ para todo $S\subset A$, em que $N(S) = \{v\in B : uv\in E \text{ para algum }u\in S\}$. Afinal, para cada $u\in S$ existe $v_u\in B$ tal que $uv_u\in M\subset E $. 

Como $M$ é um emparelhamento, tem-se ainda que $v_u \neq v_{u'}$ se $u,u'\in A$ são distintos. Nesse contexto, a propriedade "$|S|\leq |N(S)|$ para todo $S\subset A$" é dita ser a **condição de casamento** para a existência de um emparelhamento que cobre $A$. Além dela ser necessária, mostramos [[.teoremahall | aqui]] que ela é suficiente.
</WRAP>

----
<WRAP round tip box 100%>
=== Veja também: ===
  * [[.teoremahall | Condição de casamento: o Teorema de Hall]]
</WRAP>