Definíció: Két él függetlensége: nincs közös végpontja két nem hurokélnek. Élhalmaz függetlenesége: páronként független nem gurokélek. v(G) a maximális méretû párosítás nagysága. Teljes párosítás olyan M párosítás,a mley az összes csúcsot páróítja, azaz mérete |V(G)|/2.

Definíció: Lefogó ponthalmaz: olyan ponthalmaz, hogy minden élnek legyen ebbe tartozó végpontja. T(g) a minimális méretû lefogó ponthalmaz nagysága.

Megjegyzés: Minden G gráfra v(G)<=T(G).

Megjegyzés: Egy páratlan pontszámú kör mutatja, hogy az egyenlõség nem szükségszerû. Független élpár, független élhalmaz, párosítás, teljes párosítás, nu paraméter

Definíció: G gráfban lévõ M párosítás triviális bõvítése.

Definíció: Mohó párosítási algoritmus: Legyen az üreshalmaz egy kiinduló M párosításunk. A triviális bõvítés segítségével növeljük M-et, amíg tudjuk. A végeredmény a mohó algoritmus outputja.

Megjegyzés: Egyáltában nem biztos, hogy az output optimális. Következtetés: a triviális bõvítés túl egyszerû. Bonyolultabb bõvítési eljárást keresünk.

Definíció: G gráfban lévõ M párosításra vonatkozó javító út.

Lemma: A javító út élei esetén a párosításhoz tartozás és párosításon kívülre esés felcserélésével egy nagyobb párosításhoz jutunk.

Definíció: Egy M páros'ítás jávító út segítségével történõ javítását ``javító utas javításnak'' nevezzük.

Definíció: Javító utas párosítási algoritmus: Legyen az üreshalmaz egy kiinduló M párosításunk. A javító utas bõvítés segítségével növeljük M-et, amíg tudjuk. A végeredmény az algoritmus outputja.

két nagyon fontos kérdés merül fel:

I) Teljes-e a javító utas bõvítési eljárás, azaz ha nem tudjuk elvégezni, akkor biztos, hogy párosításunk maximális elemszámú? Azaz a fenti algoritmus helyes-e? A mohó algoritmus után nyilvánvaló, hogy ez egyáltalán nem nyilvánvaló kérdés.

II) A fenti algoritmus implicit módon tartalmazza a következõ problémát: Adott egy gráf és M párosítása. keressünk javító utatat. Hogyan oldható ez meg?

Az elsõ kérdésre a válasz: igen, a fenti algoritmus optimális páros'ításhoz vezet. Ezt a következõ tétel bizonyítja.

Tétel (C. Berge): Egy gráfban egy M párosítás akkor és csak akkor maximális, ha nincs rá vonatkozó javító út.

Bizonyítás: Tegyük fel, hogy van M-nél nagyobb méretû N párosítás. Ekkor G csúcsai és M, illetve N élei egy gráfot adnak, amelyben minden komponens út vagy kör. Ebben kell egy olyan komponensnek lenni, amely több N-beli élet tartalmaz mint M-belit. Ennek egy útnak kell lenni, amely G-ben egy M-re vonatkozó javító út.

A II-es kérdésre a válasz nem egyszerû. Matematikusok körülbelül 10 évig dolgoztak egy hatékony eljárás kitalálására. Páros gráfokban a keresés viszonylag egyszerûen megoldható. A továbbiakban a páros gráfok esetét külön megvizsgáljuk.