A Minimum Spanning Tree (MST) is the cheapest set of edges that connect graph vertices together. For instance, servers on a network or destinations on a road map. Stated differently, an MST is the sub-set of edges with the minimum possible sum of edge weights. A MST must satisfy two properties.

  1. Does not contain a cycle
  2. A path exists between every pair of vertices

Based on the definition of a MST, the following facts logically apply:

  • All connected graphs have at least one MST
  • There are often multiple valid MSTs for a given graph
  • An MST has $n-1$ edges.

The image below is a graphical representation of an input graph and its MST.

Minimum Spanning Tree