cut property

The fact that, for any way of splitting a graph's vertices into two groups, the cheapest edge crossing between the groups belongs to some minimum spanning tree.

In more detail

It is the exchange argument behind every greedy MST algorithm: if a tree skipped that edge, swapping it in for a dearer crossing edge would make the tree cheaper. Prim's algorithm applies it to the cut between the tree so far and everything else.

Related terms

Taught in

References