For a connected weighted undirected graph, a spanning tree is a subgraph that contains every vertex, remains connected and has no cycles.

A minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible.

An MST minimizes the cost of the whole connecting backbone. This is different from a shortest-path tree, which minimizes distances from one chosen source.

If all edge weights are distinct, the MST is unique. With equal weights, several different spanning trees can have the same minimum total cost.

A central structural fact is the cut property: for any partition of the vertices into two groups, a lightest edge crossing that cut can safely belong to some minimum spanning tree.

This property is the basis of several greedy algorithms for constructing MSTs.