Can Prim's and Kruskal's algorithms produce spanning trees of different total weight on the same graph?

## The setting Imagine a fiber build-out connecting a cluster of rural towns. Every possible trench between two towns has a surveyed cost, and you must end up with all towns connected using the cheapest total trenching. That is exactly a **minimum spanning tree (MST)** problem. Some vocabulary first, because the question turns on it: - A **spanning tree** of a connected graph is a subset of edges that touches every vertex and contains no cycle. On `n` vertices it always has exactly `n - 1` edges. - A **minimum spanning tree** is a spanning tree whose total edge weight is as small as any spanning tree's. Note the phrasing: *minimum* is defined on the **sum**, not on the identity of the edges. ## Why the totals cannot differ Both Prim's and Kruskal's algorithms are *proven* to output a minimum spanning tree — they are not heuristics or approximations. Once you accept that, the answer follows from the definition: if run A returned total `W_A` and run B returned `W_B` with `W_A < W_B`, then B's output was not minimum, contradicting B's correctness proof. So `W_A == W_B`, always. The two differ only in *how* they make a safe choice. One grows a single connected blob outward, repeatedly attaching the cheapest trench leaving the blob. The other sweeps trenches from cheapest to most expensive and accepts one whenever it joins two currently separate groups of towns. Underneath, both are applying the same safe move (the cut property): the cheapest trench crossing some split of the towns belongs to a minimum spanning tree. Different splits, same guarantee. ## Where they genuinely can differ: ties The edge *set* is not always identical. Suppose two trenches both cost 40. One algorithm might reach one of them first because of its growth order; the other might reach the sibling first because of its sort order. Both trees are minimum; both totals are equal; the drawn maps differ. That is the whole story of divergence. Formally: - **All weights distinct → the MST is unique.** Sketch: suppose two different minimum spanning trees `T1` and `T2` exist. Look at the cheapest edge that appears in one but not the other — say `e` is in `T1` only. Adding `e` to `T2` creates exactly one cycle, and that cycle must contain some edge `f` not in `T1` (otherwise `T1` would contain a cycle). Since all weights are distinct and `e` was the cheapest edge in the symmetric difference, `weight(e) < weight(f)`. Swapping `f` out for `e` gives a spanning tree strictly cheaper than `T2` — impossible. So no two distinct MSTs exist, and both algorithms must land on the same edge set. - **Ties present → possibly different edge sets, identical total.** ## Things that surprise people **Negative weights are fine here.** Unlike shortest-path algorithms that rely on costs never decreasing along a path, MST correctness rests on *comparing* edge weights. A trench with a negative cost — say a subsidy — does not break either algorithm; it just gets picked early. **Disconnected input behaves differently.** Sweeping all edges cheapest-first naturally yields a minimum spanning **forest**: one tree per connected component. Growing outward from a single start vertex only ever covers that vertex's component, so it silently returns a tree over a subset of the towns. This is a genuine behavioural difference between the two, and it is about coverage, not about weight. **Tie-breaking is not a correctness knob.** Engineers sometimes assume a "better" tie-break yields a cheaper tree. It cannot — every tie-break that respects the safe-move rule lands on the same total. Tie-breaks matter for other reasons (deterministic output across runs, preferring shorter physical spans among equal-cost trenches, reproducible diffs in an infrastructure plan), never for cost. ## What an interviewer is listening for The weak answer is "different algorithms, so probably different results" — treating greedy algorithms as heuristics that get *close*. The strong answer separates three things cleanly: the **total weight** (always equal), the **edge set** (equal unless weights tie), and the **execution order** (essentially always different). If you can also say *why* both are correct — the same cut-based safe move applied to different splits — you have shown the examiner that you understand greedy MST construction as a proof, not as two recipes to memorise.