Emparelhamento Maximal e Emparelhamento Perfeito(Máximo)
Definição: Emparelhamento Maximal
Um emparelhamento é chamado de emparelhamento maximal se nenhuma aresta do grafo puder ser adicionada sem que a propriedade de não-adjacência entre as arestas seja destruida.
Observação
Observe que um grafo pode ter vários emparelhamentos maximais. Em geral, estamos interessados no emparelhamento maximal com o maior número possível de arestas, chamado emparelhamento máximo.
Definição: Emparelhamento Perfeito
Um emparelhamento máximo é chamado de emparelhamento perfeito se todo vértice do grafo é extremidade de alguma aresta do emparelhamento.
Na figura abaixo,em $G_1$ temos um emparelhamento maximal, mas não máximo;em $G_2$ temos um emparelhamento máximo, mas não perfeito; em $G_3$ temos um emparelhamento perfeito.
