# Definition:Spanning Tree

## Contents

## Definition

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

## Sources

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