Utwórz graf w którym wierzchołki stanowiące spójne składowe zostaną ze sobą „sklejone” (nowe wierzchołki będziemy nazywać roboczo superwierzchołkami). Dopóki nie otrzymamy jednej spójnej składowej, wywołujemy kroki 1–2, za graf podstawiając graf
Po zakończeniu algorytmu jest minimalnym drzewem rozpinającym.
Dowód poprawności Lemat 1 W każdym momencie działania algorytmu, oraz po jego zakończeniu w nie będzie cyklu.
Dowód
Załóżmy nie wprost, że podczas działania algorytmu w którymś etapie pojawiła się spójna składowa, w której jest cykl. Oznaczmy ją jako Rozważmy następujące sytuacje: powstała przez połączenie dwóch superwierzchołków i Oznacza to, że do zbioru zostały dołączone krawędzie i Ponieważ ei została dołączona jako najlżejsza krawędź incydentna do więc Ale skoro ej została dołączona jako najlżejsza krawędź incydentna do to musi zachodzić (Pamiętajmy, że w grafie nie ma krawędzi o takiej samej wadze) – sprzeczność. powstała przez połączenie się trzech lub więcej superwierzchołków. Podzielmy powstały cykl na następujące części: niech będą kolejnymi superwierzchołkami należącymi do a będą kolejnymi krawędziami należącymi do które zostały dodane w zakończonym właśnie etapie algorytmu. W krawędzie oraz superwierzchołki występują na przemian.