Definition:Spanning Tree

Definition

Let $G$ be a connected graph.

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

This page or section has statements made on it that ought to be extracted and proved in a Theorem page. In particular: Move the below into its own page You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by creating any appropriate Theorem pages that may be needed. To discuss this page in more detail, feel free to use the talk page.

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$.

Also see

• Results about spanning trees can be found here.

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 4.1$: The Minimal Connector Problem: An Introduction to Trees