Back to home
Logicmojo - Updated Sept 18, 2021

A spanning tree is a subset of an undirected Graph that has all the vertices connected by minimum number of edges. If all the vertices are connected in a graph, then there exists at least one spanning tree. In a graph, there may exist more than one spanning tree.

Properties
β’ A spanning tree does not have any cycle.
β’ Any vertex can be reached from any other vertex

What is Minimum Spanning Tree?

A Minimum Spanning Tree(MST) is a subset of edges of a connected weighted undirected graph that connects all the vertices together with the minimum possible total edge weight. To derive an MST, Primβs algorithm or Kruskalβs algorithm can be used.

We found three spanning trees off one complete graph. A complete undirected graph can have maximum nn-2 number of spanning trees, where n is the number of nodes. In the above addressed example, n is 3, hence 33β2 = 3 spanning trees are possible.

β’ It is a tree (i.e., it is acyclic).
β’ It covers all the vertices V β contains |V| β 1 edges.
β’ The total cost associated with tree edges is the minimum among all possible spanning trees.
β’ not necessarily unique.

### Properties of Spanning Tree

We now understand that one graph can have more than one spanning tree. Following are a few properties of the spanning tree connected to graph G β

β’ A connected graph G can have more than one spanning tree.

β’ All possible spanning trees of graph G, have the same number of edges and vertices.

β’ The spanning tree does not have any cycle (loops).

β’ Removing one edge from the spanning tree will make the graph disconnected, i.e. the spanning tree is minimally connected.

β’ Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning tree is maximally acyclic.

Mathematical Properties of Spanning Tree

β’ Spanning tree has n-1 edges, where n is the number of nodes (vertices).

β’ From a complete graph, by removing maximum e - n + 1 edges, we can construct a spanning tree.

β’ A complete graph can have maximum nn - 2 number of spanning trees.

### Application of Spanning Tree

Spanning tree is basically used to find a minimum path to connect all nodes in a graph. Common application of spanning trees are β
β’ Civil Network Planning
β’ Computer Network Routing Protocol
β’ Cluster Analysis

The following algorithms are used to find the minimum spanning tree from a graph, which you can read about in the links below.

Prim's Algorithm
Krushkalβs Algorithm

With this article at Logicmojo, you must have the complete idea of analyzing Minimum Spanning Tree

Good Luck & Happy Learning!!