Skip to main content

Spanning Tree (Graph Theory)

If GG is a connected graph, then the Spanning Tree TGT \sube G is a minimal connected graph with V(T)=V(G)V(T) = V(G).

The edges E(G)E(T)E(G) \setminus E(T) are called the chords of TT in GG.


GG is a connected graph with G=7|G| = 7 and G=10||G|| = 10.

Figure 1 Graph G

Removing edges so that GG becomes a minimal connected graph. The chords E(G)E(T)E(G) \setminus E(T) are depicted as curved lines.

Figure 2 Spanning Tree T of G. The curved edges are the chords of T in G.