Mathwords logoMathwords

Minimum Spanning Tree — Definition, Formula & Examples

A minimum spanning tree is the cheapest way to connect every vertex of a weighted graph using edges that form no loops. You keep just enough edges to link everything, and you choose them so their total weight is as small as possible.

Let G=(V,E)G=(V,E) be a connected, undirected graph with edge weights w:E→Rw:E\to\mathbb{R}. A spanning tree of GG is a subgraph TT that contains every vertex in VV, is connected, and is acyclic. Such a tree has exactly ∣V∣−1|V|-1 edges. A minimum spanning tree (MST) is a spanning tree TT whose total weight w(T)w(T) is the smallest among all spanning trees of GG. If all edge weights are distinct, the MST is unique.

Key Formula

w(T)=∑e∈Tw(e),∣E(T)∣=∣V∣−1w(T)=\sum_{e\in T} w(e), \qquad |E(T)| = |V|-1
Where:
  • TT = a spanning tree of the graph
  • w(e)w(e) = weight (cost) of edge e
  • w(T)w(T) = total weight of the tree, which an MST minimizes
  • ∣V∣|V| = number of vertices in the graph
  • ∣E(T)∣|E(T)| = number of edges in the tree

Worked Example

Problem: A graph has vertices A, B, C, D and weighted edges AB = 1, BC = 2, AC = 3, CD = 4, BD = 5. Use Kruskal's algorithm to find a minimum spanning tree and its total weight.
Step 1: Sort the edges from lightest to heaviest. With 4 vertices, the tree needs exactly 3 edges.
AB(1), BC(2), AC(3), CD(4), BD(5)∣V∣−1=4−1=3AB(1),\ BC(2),\ AC(3),\ CD(4),\ BD(5) \qquad |V|-1 = 4-1 = 3
Step 2: Add AB and BC. Next comes AC, but A and C are already connected through B. Adding AC would create the cycle A–B–C, so you skip it.
T={AB, BC}T=\{AB,\ BC\}
Step 3: Add CD. It connects the new vertex D without a cycle. You now have 3 edges, so you stop. BD is never needed.
w(T)=1+2+4=7w(T) = 1 + 2 + 4 = 7
Answer: The minimum spanning tree uses edges AB, BC, and CD, with total weight 7.

Why It Matters

MSTs solve network-design problems directly: you can lay cable, pipe, or road to connect every site at the lowest total cost. In a college algorithms course, Kruskal's and Prim's algorithms are standard examples of greedy algorithms that provably give the optimal answer. MSTs also underlie single-linkage clustering, and they supply a 2-approximation for the metric traveling salesman problem.

Common Mistakes

Mistake: Assuming the MST gives the shortest route between any two vertices.
Correction: An MST minimizes the total weight of all its edges, not the distance between each pair of vertices. In the example, the tree path from A to D is A–B–C–D with length 7, but the route A–B–D has length 1 + 5 = 6. For point-to-point distances, use a shortest-path algorithm such as Dijkstra's.

Related Terms