200px Zostaje wybrana najkrótsza, niewybrana jeszcze krawędź – BE. 3 inne krawędzie zostają oznaczone kolorem czerwonym: BC, bo jej wybór oznaczałby powstanie cyklu BCEB, DE żeby uniknąć cyklu DEBAD i FE, żeby uniknąć cyklu FEBADF. 200px Proces postępuje analogicznie i powstaje minimalne drzewo rozpinające (wszystkie wierzchołki są połączone).
Dowód poprawności Dowód podzielony jest na dwie części. Najpierw dowodzimy, że graf generowany przez algorytm jest drzewem rozpinającym, a następnie że jest to drzewo o najmniejszej wadze.
Drzewo rozpinające Niech będzie spójnym, ważonym grafem oraz niech będzie podgrafem wygenerowanym przez algorytm. nie może zawierać cyklu, ponieważ dodana krawędź która miałaby tworzyć cykl musiałaby zostać dodana do drzewa, które jest podgrafem, a nie połączyć dwa drzewa, co jest niezgodne z algorytmem. nie może być niespójny, ponieważ pierwsza napotkana krawędź (tzn. ta o najmniejszej wadze) łącząca te składowe zostałaby wybrana przez algorytm (jej istnienie wynika z założenia, że wyjściowy graf jest spójny).