State and prove the cut property for minimum spanning trees, then use it to explain why Prim's and Kruskal's are both correct despite adding edges in completely different orders. What extra condition makes the minimum spanning tree unique?

State and prove the cut property for minimum spanning trees, then use it to explain why Prim's and Kruskal's are both correct despite adding edges in completely different orders. What extra condition makes the minimum spanning tree unique?

Approach: Take a minimum spanning tree that omits the light edge across a cut and exchange one edge, then check that both greedy algorithms only ever add edges licensed by the property.

For any cut of the vertices, the strictly lightest edge crossing it belongs to every minimum spanning tree, and both greedy algorithms only ever add such a light edge. The proof is an exchange argument: let e be the strictly lightest crossing edge and suppose a minimum spanning tree T excludes it. Adding e to T creates exactly one cycle, that cycle crosses the cut an even number of times, so it contains another crossing edge f with w(f) > w(e), and T - f + e is spanning, connected and lighter, contradicting minimality. Prim's grows one component and always takes the lightest edge leaving it, which is the light edge of the cut separating that component from the rest. Kruskal's takes the globally lightest edge joining two different components, which is the light edge of the cut separating one of those components from everything else. The same property therefore licenses both, and the different orders reach trees of equal total weight. Uniqueness holds when all edge weights are distinct, since then every cut has a strictly lightest edge; with ties several optimal trees can exist.

Follow-up: Given a minimum spanning tree, how fast can you recompute it after one edge weight decreases?

Key concepts: cut property, exchange argument, light edge, uniqueness.