Mathematics.

graph algorithms

Minimum Spanning Tree

Graph Theory30 minDifficulty4 out of 10

You should know: trees, shortest path

Overview

A spanning tree of a connected graph is a subgraph that includes every vertex and is itself a tree — connected and cycle-free, using exactly n-1 edges for n vertices. A minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible, among all spanning trees of a weighted graph. Two classical greedy algorithms compute an MST efficiently: Kruskal's algorithm sorts all edges by weight and adds each one that doesn't create a cycle, while Prim's algorithm grows a single tree outward by always adding the cheapest edge connecting the tree to a new vertex. Both are correct because of the 'cut property': the cheapest edge crossing any cut of the graph is always safe to include in some MST.

Intuition

Imagine wiring electricity to every house in a new neighborhood as cheaply as possible: houses are vertices, possible cable routes are weighted edges (cost to lay cable), and you want every house connected using the least total cable, with no wasted redundant loops. That's exactly a minimum spanning tree — the cheapest way to connect everything without any cycles (which would mean paying for cable you didn't need).

Formal Definition

Definition

For a connected weighted graph G = (V, E, w), a spanning tree T minimizes total weight among all spanning trees:

T=(V,ET), ET⊆E, ∣ET∣=∣V∣−1, T connected and acyclicT = (V, E_T),\ E_T \subseteq E,\ |E_T| = |V| - 1,\ T \text{ connected and acyclic}
Spanning tree
MST=arg⁡min⁡T∑e∈ETw(e)\text{MST} = \arg\min_{T} \sum_{e \in E_T} w(e)
Minimum spanning tree objective
Cut property: the minimum-weight edge crossing any cut (S,V∖S) belongs to some MST\text{Cut property: the minimum-weight edge crossing any cut } (S, V\setminus S) \text{ belongs to some MST}
Cut property (correctness of greedy algorithms)

Worked Examples

  1. Sort edges by weight: A-B (1), B-C (2), A-C (3).

    Sorted: A-B(1), B-C(2), A-C(3)\text{Sorted: } A\text{-}B(1),\ B\text{-}C(2),\ A\text{-}C(3)

  2. Add A-B (weight 1): no cycle, connects A and B.

    MST so far: {A-B}, weight 1\text{MST so far: } \{A\text{-}B\},\ \text{weight } 1

  3. Add B-C (weight 2): connects C, no cycle. Now all 3 vertices are connected with 2 edges — done (adding A-C would create a cycle and is skipped).

    MST: {A-B,B-C}, weight 3\text{MST: } \{A\text{-}B, B\text{-}C\},\ \text{weight } 3

Answer: MST = {A-B, B-C}, total weight 3.

Practice Problems

Difficulty 3/10

A connected graph has 7 vertices. How many edges must its minimum spanning tree have?

Difficulty 5/10

A telecom company wants to connect 5 towns with fiber cable at minimum total cost, where cost is proportional to distance. Which classical algorithm(s) solve this directly, and what greedy rule do they use?

Difficulty 4/10

If all edge weights in a connected graph are distinct, how many minimum spanning trees does the graph have?

Quiz

A minimum spanning tree of a connected graph with n vertices has exactly:
Kruskal's algorithm builds an MST by:
The cut property states that the minimum-weight edge crossing any cut (S, V∖S):

Summary

  • A minimum spanning tree connects all vertices of a weighted graph using n−1 edges at minimum total weight.
  • Kruskal's algorithm adds edges cheapest-first, skipping any that would form a cycle; Prim's grows one tree outward via the cheapest connecting edge.
  • Both algorithms are correct due to the cut property: the cheapest edge crossing any cut always belongs to some MST.

References

  1. WebsiteWikipedia — Minimum spanning tree