Minimum Spanning Tree

A minimum spanning tree is

• a tree, meaning it has no cycle
• minimum, meaning it has minimum weight
• spanning, meaning it connects all nodes

MST Problem

The MST problem takes a connected graph $G$ and outputs an MST for that graph.

Greedy Approach

The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of $T$ vs. $V-T$