# Spanning Tree

A spanning tree of a graph consists of all nodes of the graph and some of the edges of the graph so that there is a path between any two nodes.

Like trees in general, spanning trees are connected and acyclic. Usually there are several ways to construct a spanning tree.

minimum spanning tree = spanning tree whose weight is as small as possible maximum spanning tree = spanning tree whose weight is as large as possible

You have two options to find the minimum/maximum spanning tree:

### From MATH239

Spanning Tree

A

spanning treeof $G$ is a spanning subgraph of $G$ that is a tree. In other words, $V(T)=V(G),E(T)⊆E(G)$, $T$ is a tree.

**Theorems and Corollaries**

Theorem 5.2.1

A graph $G$ is Connected if and only if $G$ has a spanning tree.

Corollary 5.2.2

If $G$ is a Connected Graph with $n$ vertices and $n−1$ edges, then $G$ is a tree.

Corollary 2

Let $G$ be a graph with $n$ vertices. If any 2 of the following 3 conditions hold, then $G$ is a tree:

- $G$ is connected
- $G$ has no cycles
- $G$ has $n−1$ edges

Theorem 5.2.3

If $T$ is a spanning tree of $G$ and $e∈/E(T)$, then $T+e$ contains exactly one cycle $C$. Moreover, if $e_{′}∈E(C)$, then $T+e−e_{′}$ is a spanning tree of $G$.

Theorem 5.2.4

If $G$ is a spanning tree of $G$ and $e∈E(T)$, then $T−e$ has 2 components. If $e_{′}$ an edge in the cut induced by the vertices of one component, then $T−e+e_{′}$ is a spanning tree of $G$.