Definição

Considere um grafo bipartido $G=(V,A)$ com bipartição $\{B,C\}$. Seja $M$ um emparelhamento para esse grafo. Dizemos que um caminho que começa em $a\in B$ não emparelhado e contém arestas de $A$ e de $A\backslash M$ de forma alternada é um caminho alternante em relação a $M$. Um caminho alternante que termina em um vértice não emparelhado é chamado de caminho ampliador, pois pode ser usado para construir um emparelhamento maior.

Caminhos alternantes são usados para ampliar o emparelhamento.