Graph Theory37 sections · 1633 units
Open in Course

The Cut Property

Foundation for MST algos

The cut property states: for any cut (partition) of the graph into two sets, the minimum-weight edge crossing the cut must be in some MST. A cut divides nodes into two groups. The crossing edges connect the two groups.

Pick the lightest crossing edge. That edge will appear in at least one MST. This property is the foundation of both Kruskal's and Prim's algorithms. If you understand this, the algorithms make perfect sense.