the cut property

Suppose you split all the towns into two groups, by any line you like, with at least one town on each side. Among all the cables that would cross that dividing line, look at the single cheapest one. The cut property promises: that cheapest crossing cable belongs in some minimum spanning tree. You can include it with total confidence, no matter how you drew the line. This is the one guarantee that makes building an MST greedily safe.

Precisely: a cut partitions the vertices into two non-empty sets S and its complement. An edge crosses the cut if it has one endpoint in each set. The cut property states that if an edge e is a minimum-weight edge crossing some cut, then e is contained in some MST. The proof is a clean exchange argument. Take any MST T. If T already uses e, done. Otherwise, adding e to T creates exactly one cycle, and that cycle must cross the cut a second time via some other edge f (the cycle leaves S and must return). Since e is a cheapest crossing edge, weight(e) <= weight(f). Swap: remove f, add e. The result is still a spanning tree, and its total weight did not increase — so it is also an MST, and it contains e. Therefore some MST contains e.

The cut property is the theoretical engine behind both classic MST algorithms. Prim's algorithm applies it directly: the growing tree forms one side of a cut, and Prim always adds the cheapest edge leaving it. Kruskal's uses it too: each edge it accepts is the cheapest edge across the cut separating the two components that edge joins. A precise caveat: the property guarantees the cheapest crossing edge is in SOME MST, not necessarily in every MST, and when several crossing edges tie for cheapest, different choices can lead to different but equally optimal trees. Distinct weights make the safe edge unique and the MST unique.