Un apareamiento maximal es un apareamiento M de un grafo G con la propiedad de que si alguna arista que no pertenece a M es añadido a M, no será ya un apareamiento.