Spanning Trees
Spanning Trees
Definition: If $G$ is a graph, $H$ is a spanning subgraph of $G$ ($V(H) = V(G)$), and $H$ is a tree (connected and contains no cycles), then $H$ is said to be a Spanning Subgraph Tree of $G$, or simply a Spanning Tree of $G$. |
By the definition above, a spanning tree $H$ of a graph $G$ is a subgraph containing all vertices of $G$, is connected, and contains no cycles.
Remark: Spanning trees are not necessarily unique. For example, some graphs may have multiple spanning trees, so referring to a spanning trees as "the" spanning tree of a graph G is not generally accurate. |
For example, let's look at the following graph:

This graph has precisely $3$ spanning trees:
Spanning Tree $1$ | Spanning Tree $2$ | Spanning Tree $3$ |
---|---|---|
![]() |
![]() |
![]() |
Notice that the red, orange, and blue subgraphs above are trees (connected and acyclic) and contain all vertices in the original graph, hence, they are all spanning trees of the original graph.