Course contentsShow
← Computer Science
Lesson 1012 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Minimum Spanning Tree Definition and Properties

Understand what a minimum spanning tree is, its properties, and why it's useful in connecting graph vertices with minimum total edge weight.

Minimum Spanning Tree Definition and Properties

What you'll learn: You'll discover what a minimum spanning tree is, why it matters for connecting graphs efficiently, and the key properties that make it special.

What is a Minimum Spanning Tree?

A minimum spanning tree (MST) is a subset of edges in a weighted, undirected, connected graph that connects all vertices together with the minimum possible total edge weight, without forming any cycles.

Think of it like this: imagine you're a city planner who needs to connect several neighborhoods with power lines. You want every neighborhood connected to the grid, but you want to minimize the total length of cable used. The MST is your optimal blueprint.

Key Properties

Spanning Property

The tree must "span" all vertices—every single vertex in the original graph must be included and reachable.

Tree Property

An MST has exactly V - 1 edges (where V is the number of vertices) and contains no cycles. This is the defining characteristic of any tree structure.

Minimum Weight Property

Among all possible spanning trees, the MST has the smallest sum of edge weights. There might be multiple MSTs if different edge combinations yield the same minimum total weight.

Uniqueness Condition

If all edge weights are distinct, the MST is unique. If some edges share the same weight, multiple MSTs may exist.

Why MSTs Matter

MSTs solve real-world problems like designing efficient networks (roads, utilities, computer networks) where you need universal connectivity at minimal cost. They're also building blocks for approximation algorithms in harder problems.

Key Takeaway: A minimum spanning tree connects all vertices in a graph using V-1 edges with the smallest possible total weight, providing an optimal solution for network connectivity problems.