Niech etap -ty będzie pierwszym takim etapem, w którym coś się popsuło. Niech będzie zbiorem krawędzi przed wywołaniem etapu a będzie zbiorem krawędzi po jego wywołaniu. Niech będzie minimalnym drzewem rozpinającym takim, że ale że Istnieje więc krawędź
Fakt: Krawędź została dodana podczas -tego wywołania. (Nie może należeć do gdyż inaczej superwierzchołek do którego by należała nie byłby minimalnym drzewem rozpinającym, co jest sprzeczne z dowodem dla pierwszego etapu i założeniem, że wywołanie -te jest najmniejszym wywołaniem, które zwróciło nieoptymalne drzewa)
Dodajmy krawędź do W powstał cykl. Ponieważ jest najmniejszą krawędzią incydentną do pewnego superwierzchołka z tego cyklu, istnieje więc inna krawędź incydenta do tego samego superwierzchołka. Jednak jej waga jest większa niż waga krawędzi zatem zastąpienie jej krawędzią da nam mniejsze drzewo rozpinające co jest sprzeczne z założeniem o optymalności