Spanning Tree and Minimum Spanning Tree

A spanning tree connects all the nodes with the minimum possible number of edges without forming any loops.

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

• Includes all the vertices of the graph.
• Is connected (there’s a path between every pair of vertices).
• Contains no cycles.
• Has exactly V − 1 edges, where V = number of vertices.

Why spanning tree is Important?

A spanning tree ensures minimum structure needed to connect all nodes.
It’s widely used in network design, broadcasting, clustering, etc.

Properties of Spanning Tree

Example: Spanning Tree

Let’s say you have this connected graph.

Vertices: A, B, C, D

Edges: A – B, A – C, B – C, C – D

From this, one possible spanning tree could be:

Edges: A – B, A – C, C – D

This uses 3 edges for 4 nodes, exactly V-1 = 4 - 1 = 3 edges.

How Many Spanning Trees Are Possible?

For a complete graph (every vertex connected to every other vertex), the number of spanning trees is given by

Cayley’s formula: T(n) = nⁿ⁻² , For n vertices

Examples:

• 3 nodes → 3^(3−2) = 3
• 4 nodes → 4^(4−2) = 16
• 5 nodes → 5^3 = 125

For other graphs, you may use Matrix-Tree Theorem (Laplacian Matrix).

Operations on Spanning Tree

• Find a spanning tree (usually by DFS or BFS).
• Create a spanning tree with some weight logic leads to Minimum Spanning Tree.
• Optimize network paths using only V − 1 connections.

Types of Spanning Trees

Applications of Spanning Tree

• Computer Networks – Efficient routing between switches/routers.
• Telecommunication – Laying cables with minimum length.
• Electrical Grid – Connecting substations with minimal wiring.
• Clustering – In AI and ML (Hierarchical clustering).
• Maze Generation – Creating a perfect maze with only one solution.

Minimum Spanning Tree (MST)

A Minimum Spanning Tree is a spanning tree of a connected, weighted graph that connects all vertices with the minimum possible total edge weight and no cycles.

Why MST Is Useful?

MST is used when,

• You want to connect everything (like cities, computers, or networks),
• But you want to spend as little as possible (minimize cost/length).

It is used when you want to connect all nodes at the lowest cost.

Properties of Minimum Spanning Tree (MST)

A Minimum Spanning Tree is a tree that connects all the vertices in a connected, undirected, weighted graph with the minimum total edge weight.

Here are its important properties.

It connects all vertices: An MST includes every vertex from the original graph. There are no isolated nodes, meaning you can reach any node from any other node.

It has exactly V − 1 edges: If the original graph has V vertices, the MST will always have V − 1 edges. This is because adding any more edges would create a cycle, which is not allowed in a tree.

It does not contain cycles: As a type of tree, MST is acyclic. Any cycle in the tree would violate the "minimum" condition because removing one edge from the cycle can reduce the total weight.

It minimizes the total edge weight: Out of all possible spanning trees, the MST has the smallest possible total weight when you sum up the weights of its edges.

It is a subgraph of the original graph: The MST is formed by selecting some edges of the original graph not adding new ones. Therefore, it's a subset of the original graph’s edges.

It uses the smallest available edges carefully: The smallest edge that doesn’t form a cycle is always a candidate for the MST. This idea is used in Kruskal’s and Prim’s algorithms.

Removing an edge disconnects the MST: Since the MST has the minimum number of edges needed to stay connected, removing any edge from it will disconnect the graph.

It does not necessarily give the shortest path: While the MST connects all nodes with minimal cost, it doesn’t ensure the shortest path between any two nodes. That’s what Dijkstra’s or Bellman-Ford algorithm is for.

MST exists only in connected graphs: If the graph is not connected (i.e., some nodes can’t reach others), then you cannot have a single MST. Instead, each connected component will have its own MST, and together they form a minimum spanning forest.

Example: Minimum Spanning Tree Problem

Graph Edges: A – B (2), A – C (3), B – C (1), B – D (4), C – D (5)

MST Steps using Kruskal

Sort edges:

• B–C (1)
• A–B (2)
• A–C (3)
• B–D (4)
• C–D (5)

Add B–C (1)

Add A–B (2)

Add B–D (4)

MST complete (3 edges for 4 nodes)

Total cost = 7

Time and Space Complexity

Applications of Minimum Spanning Tree

• Network Design: Laying cables to connect all computers at minimum cost
• Electrical Grids: Wiring connections to supply power with minimal cost
• Transportation: Road/rail construction between cities
• Cluster Analysis: Data mining and Machine Learning
• Approximation Algorithm: For NP-hard problems like TSP (Travelling Salesman Problem)

Algorithms for Minimum Spanning Tree

Here's a simple list of algorithms used to find Minimum Spanning Tree (MST).

• Kruskal’s Algorithm
• Prim’s Algorithm
• Borůvka’s Algorithm
• Reverse-Delete Algorithm
• Fibonacci Heap version of Prim’s Algorithm (optimized for dense graphs)
• Cycle Property & Cut Property techniques (used in proofs and some variants)
• Randomized Algorithms (used in probabilistic or parallel approaches)