==== 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.
{{ :grafos:grafoperf.png?400 |}}