Spanning tree and Minimum spanning tree

Published by: Anil K. Panta

What is a Spanning Tree in Graph?

In graph theory, a Spanning Tree is a fundamental concept used in network design, routing, and optimization problems. Let’s understand what it is, how it works, and how it's different from a Minimum Spanning Tree (MST).

Definition: Spanning Tree

A Spanning Tree is a subset of a connected graph that:

Includes all the vertices of the graph
Uses the minimum number of edges
Has no cycles
Is still connected

If the graph has N vertices, then the spanning tree has exactly N-1 edges.

Visual Idea:

Imagine a city where intersections are nodes and roads are edges. A spanning tree is a plan where every intersection is connected with minimum roads, and no circular paths (no loops).

Properties of a Spanning Tree

Property	Description
No cycles	It must not contain loops or cycles
Exactly N-1 edges	For a graph with N vertices
Multiple spanning trees possible	A graph can have many spanning trees
Only exists in connected graphs	A disconnected graph cannot have a spanning tree
Removable edges from a complete graph	You can get a spanning tree by removing E − N + 1 edges

Cayley’s Formula:

For a complete graph with N vertices, the number of possible spanning trees is:

Total spanning trees = N(N−2)\text{Total spanning trees} = N^{(N-2)}

Example:
For N = 4 → Total = 4^(4-2) = 16 spanning trees

Real-World Applications of Spanning Trees

Network Design – Connect computers, routers, or telecom towers with minimal wiring.

Path finding algorithms – Used internally by Dijkstra’s, A*, etc.

Image segmentation – Separating parts of an image in computer vision.

Internet routing – Routing protocols build trees for efficient paths.

What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree (MST) is a type of spanning tree where the sum of edge weights is minimized.

In weighted graphs, each edge has a "cost" or "weight". An MST ensures you connect all vertices with the least total cost.

Properties of MST

Property	Description
Contains all vertices	Must include all the nodes of the graph
Has N-1 edges	If the graph has N vertices
No cycles	It’s always acyclic
Minimum total weight	Among all possible spanning trees, the total edge weight is minimum
MST may not be unique	If there are multiple edges with same weights, different MSTs may exist
Cut property	The lightest edge crossing a partition will be in MST

Example:

You are setting up Wi-Fi routers across a campus. You want maximum coverage with minimum cable cost. An MST will help you find that optimal setup.

Algorithms to Find MST

Here are four popular algorithms used to find the Minimum Spanning Tree:

1. Kruskal’s Algorithm

Sort all edges by weight
Add edges in increasing order unless they form a cycle
Use Disjoint Set Union (DSU) or Union-Find

Best for sparse graphs

2. Prim’s Algorithm

Start from any node
Use greedy method to add minimum-weight edge connecting to an unvisited node
Use priority queue / min heap

Best for dense graphs

3. Boruvka’s Algorithm

Connect components using the cheapest outgoing edge
Repeat until all vertices are connected

Good for parallel computing

4. Reverse Delete Algorithm

Start with full graph
Remove heaviest edge if it doesn’t disconnect the graph
Repeat until only a tree remains

Conceptually useful, but less efficient

Spanning Tree vs Minimum Spanning Tree

Feature	Spanning Tree	Minimum Spanning Tree
Edge Weights	Not considered	Used to find total minimum weight
Goal	Connect all vertices	Connect all with minimum cost
Unique	Can be many	Can also be many
Number of edges	N – 1	N – 1
Cycle allowed?	❌ No	❌ No

Fun Fact:

If all edges of a graph have unique weights, then the MST is unique.

Final Thought:

A Spanning Tree connects all the vertices in a graph with N-1 edges and no cycles.
A Minimum Spanning Tree (MST) is the best possible version of it — having the lowest total cost.

Knowing how MST works helps you solve real-world problems in network design, AI pathfinding, image processing, and more.