In MST construction, why is the cheapest edge crossing any vertex partition safe to take?

## What a cut is A **cut** is nothing more exotic than a way of splitting the node set into two non-empty groups, `S` and everything not in `S`. An edge **crosses** the cut when one endpoint is in `S` and the other is outside. For a network of branch offices, a cut is any line you draw that puts some offices on the left and some on the right; the crossing edges are the candidate trenches that would span that line. ## The property, stated carefully **Cut property:** for any cut, a minimum-weight edge crossing that cut belongs to *some* minimum spanning tree. If that crossing edge is *uniquely* cheapest, it belongs to *every* MST. Read the direction carefully — this is where answers go wrong. The property does **not** say the cheapest edge overall is safe from every angle, nor that every cheapest crossing edge lies in every MST, nor that an edge failing the test is necessarily excluded. It says: pick any split, pick a lightest edge across it, and you can commit to that edge without giving up optimality. ## The one-line intuition to say out loud Every spanning tree must connect the two sides, so every spanning tree uses at least one crossing edge. Suppose a tree uses a crossing edge heavier than the lightest one available. Remove the heavy edge and the tree falls into two pieces; add the light crossing edge back and the pieces rejoin, because it too has one endpoint on each side. Same number of edges, still connected, still no cycle, strictly smaller total. Therefore no minimum tree could have skipped the light edge in favour of a strictly heavier crossing edge. That exchange sentence — remove heavy, add light, still a tree, smaller total — is what interviewers want to hear before you launch into either algorithm. It is the reason greed does not need backtracking here, unlike most optimization problems where a locally cheap choice is a trap. ## Both algorithms are the same rule on different cuts **Prim's** is the cut property applied to the most obvious cut there is: `S` = the nodes already in the growing tree, and the rest outside. The algorithm's whole job is to find the lightest edge crossing that cut, which is exactly what its priority queue is for. Each step's cut is different from the last, because `S` gained a node. **Kruskal's** applies it too, less visibly. When Kruskal's accepts an edge whose endpoints are in different components, take `S` to be one of those two components. Every edge crossing that `S` is still unaccepted, and because the edge list was walked cheapest-first, the edge under consideration is a lightest one crossing that cut. Safe. When Kruskal's *rejects* an edge, both endpoints are already in the same component, so the edge crosses no relevant cut and would only close a cycle. Seeing both as one rule is the payoff: you stop memorizing two algorithms and start remembering one justification with two schedules for choosing cuts. ## The companion rule There is a mirror-image statement, the **cycle property**: for any cycle in the graph, a maximum-weight edge on that cycle can be left out of some MST; if it is uniquely heaviest on that cycle, it is in no MST. The argument is the same exchange run backwards — drop the heavy cycle edge and the cycle's remaining path still connects its endpoints. Together the two properties tell you which edges you may safely take and which you may safely discard, which is the complete decision procedure a greedy MST builder needs. ## Ties, and why they are not a footnote Trench costs, latencies rounded to milliseconds, and hop counts all produce ties in real data. With ties: - Several equal-weight edges may cross the same cut. Each is in *some* MST; none need be in all of them. - Two different runs, or two different algorithms, can return different edge sets with identical total weight. Both are correct MSTs. - If a downstream consumer wants stability across runs — a cabling plan that must not shuffle between two builds — impose a deterministic tie-break, for example ordering equal-weight edges by a stable identifier pair. That is an engineering decision layered on top of the algorithm, not a correction to it. With all weights distinct, the MST is unique and the cut property's strong form applies edge by edge: the uniquely lightest crossing edge is in the answer, full stop. ## What the property does not license It does not say "greedy always works on graphs." Change the objective — say, ask for a spanning tree minimizing the longest path between two chosen nodes, or a tree with a degree bound at every node — and the exchange argument stops going through, because removing an edge and adding another can violate the new constraint. The cut property is specifically about the total-weight objective on a spanning tree, and its narrowness is exactly why it is worth being able to state precisely rather than gesturing at "the greedy choice."