Spanning Tree

Spanning tree

A spanning tree, derived from an undirected connected graph G, encompasses all its vertices
with the minimum number of edges required. Omitting any vertex invalidates its status as a
spanning tree. Devoid of cycles and maintaining connectivity, a spanning tree is integral to
the graph structure.

In a complete graph with n vertices, the total number of spanning trees equals n(n-2). For
instance, with n = 4, the maximum number of spanning trees is 4(4-2) = 16. Thus, from a
complete graph with 4 vertices, 16 distinct spanning trees can be generated.

Let's understand the spanning tree with examples below:

Let the original graph be:




Original Graph

Some of the possible spanning trees that can be created from the above graph are:




A Spanning Tree


General Properties of Spanning Tree

1. A connected graph can yield numerous spanning trees. For a graph with n vertices, the
potential number of spanning trees is n(n-2).
2. Spanning trees are devoid of loops or cycles.
3. Spanning trees consist of n vertices and n-1 edges.
4. All spanning trees within a graph share identical vertices.
5. Eliminating a single edge from a spanning tree results in graph disconnection, as
spanning trees are minimally connected.

Page 1 of 2