Se $G = (V,E)$ é um grafo bipartido com partes $A$ e $B$, observa-se que, para que exista um 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 aqui que ela é suficiente.