Minimum Spanning Trees

Graph Theory · Axiom Academy

Understanding weighted graphs and the fundamental properties that enable efficient MST algorithms 1. Weighted Graphs and MST Definition A weighted graph assigns a numerical cost or weight to each edge. A spanning tree connects all vertices using exactly n-1 edges (where n is the number of vertices), forming a connected acyclic subgraph. The animation below shows a weighted graph and highlights one of its minimum spanning trees. An MST is unique when all edge weights are distinct. However, when multiple edges have the same weight, different MSTs may exist with equal total weight. The animation demonstrates a graph with duplicate edge weights, showing two different MSTs with the same total cost. A cut is a partition of the graph's vertices into two disjoint sets. The cut property is fundamental to MST algorithms: This property guarantees that greedily selecting the lightest edge across any cut will build toward an MST. Algorithms like Prim's and Kruskal's exploit this principle. While the cut property tells us which edges to include, the cycle property tells us which edges to exclude: This property is the dual of the cut property and ensures we avoid creating cycles with unnecessarily heavy edges. It forms the basis for "reverse-delete" MST algorithms.

This is the written version of the interactive lesson above. See the full Graph Theory course.