Ein Spannbaum eines zusammenhängenden Graphen $G$ ist ein Teilgraph, der alle Knoten von $G$ enthält und ein Baum ist, das heißt, er ist zusammenhängend und zyklenfrei.
Ein Spannbaum $T$ eines Graphen $G = (V, E)$ hat die Eigenschaften:
Gegeben sei der Graph $G$:
Ein möglicher Spannbaum $T$ aus $G$ könnte sein: