Tegyük fel, hogy algoritmusunk úgy fut, hogy a segédgráfban talált minimális költségű párosítás mögé nézve olyan utakhoz jutunk amelyek nem éldiszjunktak. Azaz az x és x' csúcsok közti P, illetve y és y' csúcsok közti Q út is az optimális párosítás két élenek felel meg, de az utaknak van közös éle, egy a és b csúcsok közötti él.

A P és Q utak diszjunkt uniójából hagyjuk el az a és b csúcsok közötti két élt. Ezzel egy olyan S gráfhoz jutunk, amelyben négy páratlan fokú; csúcs van: x,x',y,y'. S gráfban kell két útnak lenni, P' és Q', amelyek éldiszjunktak és végpont párjaikkal párosítják az x,x',y,y' pontnégyest.

A P' és Q' utak összhossza ``megveri '' a kiinduló P,Q útpárét. Ez ellentmondás, ami azt mutatja, hogy algoritmusunk futása során automatikusan éldiszjunkt utakhoz jutunk.

Vissza