Definition:Spanning Tree

From ProofWiki
Jump to: navigation, search


Let $G$ be a connected graph.

A spanning tree for $G$ is a spanning subgraph of $G$ which is also a tree.

Clearly a tree is its own spanning tree:

As a tree $T$ of order $n$ has $n-1$ edges, its spanning tree must also contain $n-1$ edges, and those must be the same ones as in $T$.

Creation of a Spanning Tree

There are two ways of creating a spanning tree for a given graph $G$:

Building-Up Method

Start with the edgeless graph $N$ whose vertices correspond with those of $G$.

Select edges of $G$ one by one, such that no cycles are created, and add them to $N$.

Continue till all vertices are included.

Cutting-Down Method

Start with the graph $G$.

Choose any cycle in $G$, and remove any one of its edges.

By Condition for Edge to be Bridge, this will not disconnect $G$.

Repeat this procedure till no cycles are left in $G$.