Spanning Tree and Minimum Spanning Tree: Detailed Notes, Examples & FAQs

What is a Spanning Tree?

A spanning tree is a subgraph that connects all vertices of a connected, undirected graph without forming any cycle.

A minimum spanning tree, or MST, is a spanning tree with the minimum possible total edge weight.

This page focuses on spanning tree and MST concepts. Prim's and Kruskal's algorithms have their own dedicated detailed pages.

A spanning tree of a connected, undirected graph is a subgraph that includes every vertex of the original graph and is also a tree. Since it is a tree, it must be connected and must not contain any cycle.

The word spanning means all vertices are covered. The word tree means the selected edges connect those vertices without cycles. So a spanning tree is the simplest connected version of the original graph.

It contains all vertices of the graph.
It uses only some edges from the original graph.
It is connected, so every vertex is reachable from every other vertex.
It is acyclic, so it has no closed loop.
If the graph has V vertices, every spanning tree has exactly V - 1 edges.

Example Graph

Suppose a graph has vertices A, B, C, and D with these edges:

Edge	Weight
A - B	4
A - C	3
B - C	2
B - D	5
C - D	7

Possible Spanning Trees

The graph has 4 vertices, so every spanning tree must contain exactly 3 edges. Different valid choices are possible.

Tree	Selected Edges	Total Weight	Valid?
T1	A-B, B-C, B-D	4 + 2 + 5 = 11	Yes, all vertices connected and no cycle
T2	A-C, B-C, B-D	3 + 2 + 5 = 10	Yes, all vertices connected and no cycle
T3	A-B, A-C, C-D	4 + 3 + 7 = 14	Yes, all vertices connected and no cycle
Not a tree	A-B, A-C, B-C	9	No, vertex D is missing and A-B-C forms a cycle

Properties of Spanning Tree

Property	Explanation
Contains all vertices	No original vertex is excluded from the spanning tree
Has V - 1 edges	A tree with V vertices always contains V - 1 edges
No cycles	Adding any extra edge to a spanning tree creates a cycle
Connected	Removing any selected edge disconnects the tree
Can be multiple	One graph can have many different spanning trees
Uses original edges only	A spanning tree cannot invent a new edge that was not in the graph

Spanning Tree vs Graph vs Tree

Concept	Meaning	Can Have Cycles?	Must Include All Original Vertices?
Graph	General structure of vertices and edges	Yes	It is the original structure
Tree	Connected graph with no cycle	No	Not necessarily tied to another graph
Spanning Tree	Tree formed from a graph that covers all vertices	No	Yes

What is a Minimum Spanning Tree?

When a connected, undirected graph has edge weights, every spanning tree has a total weight. A minimum spanning tree is the spanning tree whose total edge weight is as small as possible.

Every MST is a spanning tree, but not every spanning tree is an MST. The MST is the cheapest valid way to connect all vertices.

MST applies to weighted, undirected, connected graphs.
The goal is minimum total edge weight.
The final result still contains exactly V - 1 edges.
The result must connect every vertex.
The result must not contain a cycle.

MST Example from the Same Graph

From the example graph, compare the valid spanning trees by total weight.

T1 total weight = 11.
T2 total weight = 10.
T3 total weight = 14.
Among these choices, T2 is better because it has the smallest total weight.
For the full graph, the MST is A-C, B-C, B-D with total weight 10.

Spanning Tree vs Minimum Spanning Tree

Point	Spanning Tree	Minimum Spanning Tree
Meaning	Any tree that connects all vertices	The spanning tree with minimum total weight
Weights required?	No	Yes, weights are needed for comparison
Number of edges	V - 1	V - 1
Cycle allowed?	No	No
Can be many?	Yes	Yes, if equal weights allow ties
Main concern	Connectivity without cycles	Connectivity with least total cost

Cut Property

The cut property is the main idea behind MST algorithms. If we divide the vertices into two non-empty groups, the lightest edge crossing between those groups is safe to include in some MST.

A cut separates the graph vertices into two parts.
A crossing edge has one endpoint on each side of the cut.
The minimum-weight crossing edge is safe for an MST.
Prim uses this idea when it chooses the cheapest edge leaving the current tree.
Kruskal also relies on safe edges while merging components.

Cycle Property

The cycle property says that if a cycle exists in a weighted graph, the heaviest edge in that cycle is not needed for an MST when it is strictly heavier than the alternatives.

A spanning tree cannot contain a cycle.
If a cycle appears, at least one edge must be removed.
Removing the heaviest edge from a cycle keeps the graph cheaper or equally cheap.
This explains why expensive cycle-forming edges are skipped.

When Spanning Tree Exists

Graph Type	Spanning Tree Exists?	Reason
Connected undirected graph	Yes	All vertices can be connected
Disconnected graph	No single spanning tree	At least one vertex group is unreachable from another
Unweighted connected graph	Yes	Weights are not required for a normal spanning tree
Weighted connected graph	Yes	Also allows MST comparison
Directed graph	Not in the classical MST sense	Directed graphs use different structures such as arborescences

Number of Edges Rule

For any spanning tree:

If the original graph has V vertices, the spanning tree has V - 1 edges.
If it has fewer than V - 1 edges, it cannot connect all vertices.
If it has more than V - 1 edges and remains connected, it must contain a cycle.
This rule is often the fastest way to check whether a proposed answer can be valid.

Formula

Number of edges in a spanning tree = V - 1

If V = 6:
Required spanning tree edges = 6 - 1 = 5

Applications of Spanning Tree and MST

Spanning trees are useful whenever we need connectivity with no redundant cycles. MSTs are useful when each connection has a cost.

Application	How It Helps
Network design	Connect all routers or computers with minimum cable cost
Road planning	Connect cities while minimizing construction cost
Electrical grids	Connect stations with minimum wiring
Clustering	Build an MST and remove heavy edges to form groups
Broadcasting	Send data to all nodes without repeated loops
Approximation algorithms	MSTs provide useful structure for harder optimization problems

Algorithms Used to Find MST

This page explains the concept. Use the dedicated pages below for full algorithm steps, dry runs, and code.

Algorithm	Basic Idea	Dedicated Page
Kruskal's Algorithm	Sort edges and add the cheapest safe edge	daa/kruskals-minimum-spanning-tree
Prim's Algorithm	Grow one tree using the cheapest outgoing edge	daa/prims-minimal-spanning-tree

Spanning Tree Failure Cases

Thinking a spanning tree can skip a vertex. It must include all vertices.
Including a cycle in a spanning tree. A tree cannot contain a cycle.
Using V edges instead of V - 1 edges.
Calling every spanning tree an MST. Only the minimum-weight one is an MST.
Applying MST directly to directed graphs without checking the correct directed concept.
Confusing MST with shortest path. MST minimizes total connection cost, not distance from one source.

Spanning Tree Rules

A spanning tree connects all vertices using no cycles.
Every spanning tree of V vertices has exactly V - 1 edges.
A graph can have many spanning trees.
An MST is the spanning tree with minimum total edge weight.
Cut and cycle properties explain why greedy MST algorithms work.
Study Prim and Kruskal separately for implementation details.

Reject a Cycle While Building a Minimum Spanning Tree

edges = [(1, 2, 1), (2, 3, 2), (1, 3, 4)]
parent = {node: node for node in (1, 2, 3)}

def find(node):
    while parent[node] != node:
        parent[node] = parent[parent[node]]
        node = parent[node]
    return node

tree = []
for left, right, weight in sorted(edges, key=lambda edge: edge[2]):
    root_left, root_right = find(left), find(right)
    if root_left != root_right:
        parent[root_right] = root_left
        tree.append((left, right, weight))

print(tree)

Output

[(1, 2, 1), (2, 3, 2)]

Before you move on