Futtassuk a javító út kezdeményeket növelő algoritmust úgy, hogy a kiinduló pontok R halmaza az összes párosítatlan csúcs. Így a keresés eleve sikertelen: kizárt, hogy egy párosítatlan csúcsot címkézzünk meg. Az algoritmusunk outputja egy maximális kereső erdő.
Ezekután a külső pontok közötti éleket vizsgáljuk.
1.eset: Létezik a kereső erdő két különböző komponensbveli csúcs közötti él. Ezen él mentén a keersés által megtalált két javító út kezdemény egy javító úttá olvasztható össze. A keresés sikeres.
2.eset: Külső pontok között nincs él: Ekkor a belső pontok egy Tutte-akadály adnak, amely bizonyítja, hogy aktuális párosításunk optimális, nincs javító út, a keresés sikertelen.
3.eset: Külső pontok között van egy él, de egy kereső fán belül. Ez az e él egy kört definiál a fa éleivel. Ezen kör élhalmazát három részre bonthatjuk: az e él, és két ív, amely az e él két végpontjából a kereső fa gyökerébe vezető két út osszetalákozásáig vezeteő egy-egy szakasza. A két ív talákozási pontja egy külső pont. Ekor ezen kör csúcsit egy ponttá ejtjük össze úgy, hogy a köztük vezető élek eltűnnek.
Megjegyzés: Páros gráfok esetén ez az eset nem lehetséges.
Legyen G' az így kapott gráf. A G gráf élei közül néhány eltünt és néhány megmaradt mint a G' gráf élei. Ennek megfelelően beszélhetünk M'-ről az M párosítás megmaradt éleiről és F'-ről a kereső erdő megmaradt éleiről.
Lemma:
(i) M' egy párosítás G'-ben
(ii) F' egy kereső erdő M'-re nézve.
Bizonyítás: Egyszerű.
Megjegyzés: F' nem biztos, hogy maximális az M' párosításra nézve.
Az algoritmus ezek után a címkézés kiterjesztő lépéssel kezdve meghívja önmagát a (G', M', F') hármassal. A rekurzív algoritmus outputja egy javíto' út egy (esetleg többszörösen) zsugorított gráfban vagy egy Tutte-akadály egy (esetleg többszörösen) zsugorított gráfban. A következő két lemma adja az Edmonds-algoritmus hiányzó lépéseit és a helyesség igazolását.
1. lemma: Ha a H többszöorösen zsugorított gráfban van javíto út,a kkor G-ben is van és ez algoritmikusan megtalálható.
2. lemma: Ha H-ban, egy többszörösen zsugorított gráfban a belső pontok Tutte-akadályt adnak, ami bizonyítja az aktuális párosítás optimalitását, akkor a belső pontok ősei az eredeti gráfban Tutte-akadályt adnak, ami M optimalitását igazolják.
Megjegyzés: A jegyzetben egy konkrét példa analízise látható az Edmonds-algoritmus esetén. Ennek követése ajánlott.