Definição

Um conjunto $M$ de arestas independentes em um grafo $G=(V,A)$ é chamado de emparelhamento. Os vértices de tais arestas são chamados de emparelhados. $M$ é um emparelhamento de $U \subseteq V$ se todo vértice em $U$ é incidente com uma aresta em $M$. Os vértices em $U$ são então chamados de emparelhados (por $M$); vértices não incidentes com uma aresta de $M$ são desemparelhados.

Em outras palavras, um emparelhamento de um grafo $G=(V,E)$ é um subconjunto $M \subseteq E$ tal que nenhum par de arestas de $M$ incide no mesmo vértice. </WRAP> —–