A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected..

**Rules:**

- It is a connected tree
- It has no cycle
- Select all vertices (compulsory)
- Number of edges selected based on number given to the edges

So, Spanning Tree => AB (2) + BC(1) + CD(3)

=> 1+2+3

=> 6

**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 **n ^{n-2}** number of spanning trees where

**n**is the number of vertices in the graph

Suppose, if **n = **4, the number of maximum possible spanning trees would be **5 ^{4-2} = 25.**

Thus, we can conclude that spanning trees are a subset of connected Graph G and disconnected graphs do not have spanning tree.

**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
- Water-supply networks
- Telecommunication networks, and electrical grids.

**Minimum Spanning Tree (MST)**

In a weighted graph, a minimum spanning tree is a spanning tree that has minimum weight than all other spanning trees of the same graph. In real-world situations, this weight can be measured as distance, congestion, traffic load or any arbitrary value denoted to the edges.

**Minimum Spanning-Tree Algorithm**Two most important spanning tree algorithms here − Both are greedy algorithms.

- Kruskal’s Algorithm
- Prim’s Algorithm

Kruskal’s Algorithm | Prim’s Algorithm |
---|---|

Kruskal’s algorithm also follows greedy approach, which finds an optimum solution at every stage instead of focusing on a global optimum | It is a greedy algorithm that starts with an empty spanning tree. |

This algorithm is also used to find the minimum spanning tree for a connected weighted graph. | It is used to find the minimum spanning tree from the graph. |

Find the minimum spanning tree using Kruskal’s Algorithm Step 1: Sort edge valuesStep 2: Remove the Cyclic Step 3: Draw edge with low weighted edge values Step 4: Sum of all edge values | Find the minimum spanning tree using Prim’s Algorithm Step 1: Start from Low weighted values from vertexStep 2: Remove the Cyclic Step 4: Sum of all edge values |