Si chiamerà  Accoppiamento M di un grafo  un sotto insieme di archi con la proprietà che questi non siano fra loro adiacenti. Dato un grafo, è possibile trovare vari tipi di accoppiamenti. L’obiettivo principale di questo problema risulta la ricerca dell’Accoppiamento Massimo cioè quello di massima cardinalità che coinvolge più archi possibili. Sullo stesso grafo è  possibile individuare  più accoppiamenti. 
Uno può  risultare il massimo ottenibile poiché coinvolge, nella costruzione, esattamente 5 nodi sui 10 totali. Un numero che è uguale alla metà della cardinalità del grafo. In questo caso l’accoppiamento si dirà completo o perfetto. Dato un accoppiamento M, tutti gli archi appartenenti ad M vengono detti accoppiati, gli altri non appartenenti sono chiamati liberi. Analogamente i nodi che individuano gli archi appartenenti ad M sono detti accoppiati mentre gli altri che non hanno nessun arco di M incidente si denominano scoperti. Un percorso   è chiamato alternante se forma un cammino che parte da un nodo scoperto ed è costituito, alternativamente, da un arco non appartenente all’accoppiamento e da uno appartenente. La ricerca della soluzione migliore richiede essenzialmente la necessità di estrapolare dal grafo assegnato un cammino tra due nodi scoperti lungo cui è possibile aumentare la cardinalità dell’accoppiamento. Un cammino alternante tra due nodi scoperti viene definito Aumentante. Pertanto in un cammino aumentante, il numero di archi che fanno parte dell’accoppiamento risulta uno di meno degli altri archi. Ovviamente, dato un accoppiamento di cardinalità  i  è chiaro che, se si riesce ad individuare un cammino aumentante, si può facilmente ottenere una soluzione migliore scambiando gli archi che fanno parte dell’accoppiamento con gli altri. Poiché questi ultimi sono uno in più, otteniamo una soluzione di cardinalità  i+1. 
Per quanto concerne la cardinalità, sussiste il seguente : 

Lemma 1 :
Dato P=[u1,u2,...uk]  un insieme di archi su un percorso aumentante in un grafo G rispetto all’accoppiamento M allora   M'=M~P (con ~  si  indica la differenza simmetrica) è un accoppiamento di cardinalità  /M/+1. 

Segue il significativo teorema sulla ricerca della cardinalità massima ottenibile per un accoppiamento su un grafo: 

Teorema 1 :
Un accoppiamento  M  in un grafo  G  è di massima cardinalità se e solo se non ammette nessun cammino aumentante.

Il teorema appena visto rappresenta una caratterizzazione dell’accoppiamento massimale. Per trovare un accoppiamento massimale, molti algoritmi si basano sulla ricerca iterata di un cammino aumentante. L’esecuzione viene bloccata quando non è più possibile trovare un cammino maggiorante. Il punto di partenza per questo tipo di algoritmi è quello di accettare come cammino iniziale una soluzione vuota.