Nechť $G = (V, E)$ je souvislý graf.
Podgraf $K$ nazveme kostrou grafu $G$, pokud
$V(K) = V(G)$
$K$ je strom
Nesouvislé grafy nemají kostru, kostru má každá souvislá komponenta.
Kostra souvislého grafu je tedy souvislý podgraf nad stejnou množinou vrcholů s nejmenším počtem hran.
Souvislý graf s kružnicemi má více různých koster, např.
BFS_kostra)
Nechť $G = (V, E)$ je souvislý graf.Potom hrany do předchůdců v BFS tvoří nějakou kostru grafu $G$.
Označme $H$ graf na množině vrcholů $V$ s hranami do
předchůdců (podle pole vyplněného algoritmem BFS).
Víme, že každý vrchol kromě počátečního vrcholu má právě jednoho předchůdce. Tedy $H$ má právě $n − 1$ hran.
Se znalosti BFS bude určitě platit, že po hranách do předchůdců je možné se z každého vrcholu
dostat do $s$ (kde $s$ je počáteční vrchol BFS), neboli pro každý vrchol v existuje v $H$ sled z $v$ do $s$ a protože složením sledů vznikne sled, je graf $H$ souvislý.
$\square$