Why is the cheapest edge crossing any cut of a weighted graph safe to put in a minimum spanning tree?
answer
- start from any split of the vertices
- assume an optimal tree that omits the edge
- adding one edge makes exactly one cycle
- that cycle must cross back over the split
- swap the two crossing edges and compare
basics
~20 sAn exchange argument proves it: adding that edge to any minimum spanning tree creates exactly one cycle, and that cycle must contain another edge crossing the same cut. Swapping them keeps the tree spanning and never increases total weight.
solid answer
~50 sTake any split of the vertices into two non-empty groups — that is a cut — and let `e` be the cheapest edge with one endpoint on each side. Claim: some minimum spanning tree contains `e`. Suppose a minimum spanning tree `T` omits it. Adding `e` to `T` creates exactly one cycle, and a cycle that leaves one side of the cut must come back, so it contains a second crossing edge `f`. Since `e` is cheapest across the cut, `weight(e) <= weight(f)`. Swap `f` out for `e`: still spanning, still acyclic, total weight no larger — so the result is also a minimum spanning tree, and it contains `e`. If `e` is *strictly* cheapest across the cut, it is in **every** minimum spanning tree. This one lemma is the safe move behind both classic greedy constructions.
go deeper
Be ready to say what a cut is — any split of the vertices into two non-empty groups — and that the cheapest edge crossing it can be taken without regret.
Walk the exchange argument out loud: assume an optimal tree without the edge, add it, use the single cycle it creates, find the other crossing edge, swap, and compare weights.
Show where the property is load-bearing in real decisions: it survives negative and zero weights, it degrades to some-tree-not-every-tree under ties, and it is the reason two very different constructions cost the same.
Own the framing that a greedy algorithm without a safe-move lemma is a guess. Be able to say what evidence you would demand before signing off on any greedy choice in a design review.
## The claim, stated precisely A **cut** is any split of the vertex set into two non-empty groups, `S` and everything else. An edge **crosses** the cut if it has one endpoint in each group. **Cut property.** For any cut, a minimum-weight crossing edge belongs to *some* minimum spanning tree. If that crossing edge is *strictly* lighter than every other crossing edge, it belongs to *every* minimum spanning tree. That second sentence is the part candidates usually drop, and it is where ties live. ## Why a skeptic should believe it Put it in a fiber build-out: the towns already wired form group `S`, the rest of the region is the other side. The cheapest trench crossing that frontier costs 40; a project manager asks the natural question — "how do you know that committing to this 40 now doesn't force a 200 later that a smarter plan would have avoided?" The answer is an **exchange argument**, and it is short enough to say out loud: 1. Let `T` be *any* minimum spanning tree — including the hypothetical smarter plan. If `T` already contains `e`, we are done. 2. Otherwise add `e` to `T`. A spanning tree on `n` vertices has exactly `n - 1` edges and no cycle; adding one more edge creates **exactly one** cycle, namely `e` plus the unique existing path between its endpoints. 3. That path starts on one side of the cut and ends on the other, so somewhere along it there is a second edge `f` crossing the same cut. 4. `e` is a minimum-weight crossing edge, so `weight(e) <= weight(f)`. 5. Remove `f`. Removing an edge from the single cycle leaves the graph connected and acyclic — a spanning tree again. Its total weight is `weight(T) - weight(f) + weight(e) <= weight(T)`. 6. `T` was minimum, so the new tree is minimum too, and it contains `e`. So committing to the 40 never costs you anything. There is always an optimal plan that agrees with that decision. If the 40 was the unique cheapest crossing, step 4 becomes a strict inequality, the new tree would be *strictly* cheaper than `T` — impossible — so no minimum spanning tree can omit `e` at all. ## How the two classic constructions instantiate it Both greedy minimum-spanning-tree algorithms are the same lemma applied to different cuts: - Growing a single connected region outward uses the cut **(region built so far, everything else)** and takes the cheapest edge across that frontier. - Sweeping edges cheapest-first and accepting one whenever it joins two separate groups uses the cut **(one of those groups, everything else)**. The heavier edges rejected along the way had both endpoints inside a single group — they crossed nothing. This is why the two algorithms feel unrelated but are provably interchangeable in cost: the safe move is identical, only the choice of cut differs. ## What the property does *not* say - It does not say a greedy choice is safe *regardless of the cut* — the edge must be minimum across a cut that actually separates something. An edge internal to one side proves nothing. - It does not say the resulting tree is unique. Ties across a cut mean several safe edges, hence potentially several minimum spanning trees of equal total weight. - It does not require positive weights. The argument is a **comparison** between `weight(e)` and `weight(f)`; negative weights, zeros and subsidies compare fine. This is a real point of contrast with greedy shortest-path search, whose safety argument needs costs never to decrease as a path grows — there, a single negative edge is fatal. - It does not depend on the graph being sparse, dense, or metric. Any weighted connected graph works. ## The mirror-image lemma There is a companion worth knowing: the **cycle property** — for any cycle, a strictly heaviest edge on that cycle is in no minimum spanning tree. It is the same exchange argument run backwards, and it is what justifies *rejecting* an edge rather than accepting one. Cut property = safe to take; cycle property = safe to discard. Together they explain every decision either greedy construction makes. ## What an interviewer is listening for Weak answers wave at "greedy works here" or assert the property as a memorised fact. Strong answers produce the exchange argument in five or six sentences, land the phrase "adding an edge to a spanning tree creates exactly one cycle," and volunteer the tie caveat — *some* minimum spanning tree in general, *every* one when the crossing edge is strictly cheapest. That is the difference between having read that greedy is correct here and being able to defend it to someone who doubts you.
- Does the cut property still hold if two edges tie for cheapest across the cut?Yes, but the guarantee weakens. With a tie, each tied edge is in *some* minimum spanning tree, not in every one — the exchange argument gives `weight(e) <= weight(f)` instead of a strict inequality, so the swap produces an equally good tree rather than a contradiction. Ties are exactly why two correct constructions can return different edge sets of identical total weight.
- Which cut is each classic greedy construction applying the property to?Growing outward from a start vertex uses the cut between the region built so far and everything else, and takes the cheapest edge across that frontier. Sweeping edges cheapest-first uses the cut around one of the two groups an accepted edge merges; the heavier edges it skipped had both endpoints inside a single group, so they crossed nothing and the property never applied to them.
- Is there a matching rule for rejecting an edge rather than accepting one?Yes — the cycle property: on any cycle, a strictly heaviest edge lies in no minimum spanning tree. It is the same exchange argument in reverse, since you could always drop that edge and reconnect using the rest of the cycle for less. Cut property justifies taking an edge; cycle property justifies discarding one.
You are wiring a region town by town. Committing to the cheapest trench across the current frontier is like taking the cheapest ferry across a river: any plan that crossed elsewhere can be rewritten to use your crossing instead, and it never comes out more expensive.
saying these in an interview costs you the question
- Greedy here is a heuristic, so the tree is approximate
- The cut property needs all weights to be positive
- Adding one edge to a spanning tree creates several cycles
- The cheapest edge anywhere is always safe to take
- It guarantees the minimum spanning tree is unique