Množina hran $M\subseteq E$ je rozšířitelná do minimální kostry, pokud existuje minimální kostra $T$ obsahující hrany $M$.

Meta-algoritmus: Postupně budeme konstruovat množinu $M$ rozšířitelnou do minimální kostry. Začneme s prázdnou množinou $M$. Podle následujícího lemmatu [ref]lemma_o_existenci_rezu[/ref] (o existenci řezu) najdeme řez neobsahující hranu $M$ a podle lemmatu [ref]lemma_o_nejlevnejsi_hrane_rezu[/ref] (o nejlevnější hraně řezu) do kostry přidáme nejlevnější hranu tohoto řezu. Tento krok zopakujeme $(n-1)$-krát až skončíme s minimální kostrou.

Lemma (o existenci řezu): Nechť $M\subseteq E$ je množina rozšířitelná do minimální kostry, která ještě není minimální kostrou, pak existuje řez $\delta(A)\not=\emptyset$ takový, že $\delta(A)\cap M=\emptyset$.
Důkaz: Zvolme si libovolný vrchol $x$ a nechť $A$ je množina vrcholů, do kterých z $x$ vede cesta po hranách ležících v $M$. Jinými slovy $A$ je komponenta souvislosti $M$ obsahující $x$. Protože $M$ není minimální kostrou, tak existuje vrchol $y\not\in A$. Protože graf $G$ je souvislý, tak existuje cesta $xPy$. Jelikož $x\in A$ a $y\not\in A$, tak cesta $xPy$ obsahuje hranu $e\in \delta(A)$. Ta dokazuje že $\delta(A)\not=\emptyset$.

Následující lemma o nejlevnější hraně neříká nic složitějšího, než že nejlevnější hrana každého řezu patří do minimální kostry. Problémek ovšem nastane, pokud je těch nejlevnějších hran v řezu více. Potom do kostry můžeme dát kteroukoliv z nich, ale nejvýše jednu. Pojem rozšířitelnost do minimální kostry hlídá, jestli už jsme do $M$ nepřidali jinou nejlevnější hranu téhož řezu (řez nesmí obsahovat žádnou hranu $M$).

Lemma (o nejlevnější hraně řezu): Nechť $M\subseteq E$ je množina rozšířitelná do minimální kostry a $e$ je nejlevnější hrana řezu $\delta(A)$ splňujícího $\delta(A) \cap M=\emptyset$. Pak je i množina $M\cup\{e\}$ rozšířitelná do minimální kostry.
Důkaz: $M$ je rozšířitelná do minimální kostry a proto existuje minimální kostra $T$ obsahující hrany $M$. Pokud $e\in T$ tak jsme hotovi. Podívejme se na opačný případ $e\not\in T$. Označme si konce hrany $e$ pomocí $u$ a $v$. Mezi $u$ a $v$ existuje v $T$ jednoznačně určená cesta $uTv$. Jelikož $u\in A$ a $v\not\in A$, tak na cestě $uTv$ existuje hrana $f\in \delta(A)$. Cesta $uTv$ spolu s $e$ tvoří kružnici, proto i $T’=T-f+e$ tvoří kostru. Navíc $c(T‘)=c(T)-c(f)+c(e)$. Protože $c(e)\leq c(f)$, je i $c(T‘)\leq c(T)$ a $T’$ je minimální kostra obsahující $M\cup\{e\}$.

Uvedený meta-algoritmus je konečný, protože v každém kroku přidá do $M$ jednu hranu a každá kostra má právě $n-1$ hran. Podle indukce a lemmatu (o nejlevnější hraně řezu) bude množina $M$ opravdu minimální kostrou.

Všechny používané algoritmy na nalezení minimální kostry se liší akorát tím, jakým způsobem procházejí vhodné řezy a také tím, jak v nich najdou nejlevnější hranu. Stačí uvažovat řezy určené jednou nebo více komponentami souvislosti $M$. Ostatní řezy obsahují hranu $M$ a proto nevyhovují předpokladům lemmatu o nejlevnější hraně řezu.


Ukážeme si tři přístupy: