Articles
Minimum Spanning Tree Interview Questions: Cut Properties and Competing Solutions
Practice minimum spanning tree interview questions with cut proofs, equal-weight alternatives, Kruskal and Prim traces, and independent optimality checks.
Two candidates return different edge sets for a minimum spanning tree. One costs four, the other also costs four, and both connect every vertex without a cycle. Declaring one wrong because it differs from your expected list confuses an optimal objective with a unique answer.
Minimum spanning tree interview questions test whether you can justify safe choices and compare competing solutions under the actual graph contract. Start with what is being minimized, then explain why an edge can be selected and how the final result can be checked.
Technical reference facts below come from Princeton's algorithm authors and the official NetworkX API, checked September 30, 2026. Worked graphs, checks and interview advice are original examples and inference. No candidate reports establish a particular employer's question frequency or interview format.
What objective does an MST actually minimize?
Reference fact: an MST is a spanning tree of a connected, undirected, weighted graph with minimum sum of selected edge weights. A disconnected graph instead admits a minimum spanning forest, containing an MST for each connected component. Princeton MST definitions
State whether the task requires one connected tree or permits a forest. For a connected graph with V vertices, a tree contains V−1 edges. For a forest spanning c connected components, it contains V−c edges. A low sum without coverage is not a solution; a connected subgraph with extra cycle edges is not a tree.
Use this original triangle to separate objectives: AB costs 2, BC costs 2 and AC costs 3. The MST selects AB and BC, total 4. Its route from A to C costs 4. A shortest-path tree rooted at A selects AB and AC, total 5, preserving A→C's shortest distance of 3.
Both answers are correct for their own objectives. An MST minimizes network construction weight, not every source-to-destination route. A directed graph, capacity requirement or fault-tolerant network may require a different model altogether. Clarify those requirements before applying a familiar greedy algorithm.
What does the cut property prove when weights tie?
Reference fact: Princeton presents the cut property under distinct edge weights: the lightest crossing edge belongs to the unique MST. Its chapter explicitly notes that equal weights can allow multiple MSTs and that its algorithms still work with ties. Cut-property assumptions
For an original proof exercise with ties, let F be the edges already selected and assume F can be extended to an MST. Choose a cut that respects F: none of F's edges crosses it. Let e be a minimum-weight edge crossing that cut.
Take an MST T containing F. If T already contains e, the choice is safe. Otherwise, adding e creates a cycle. The cycle includes another crossing edge f. Because e is lightest across the cut, its weight is at most f's. Replacing f with e preserves a spanning tree and cannot increase cost. Since the cut respects F, f was not an already selected edge that must be retained.
This proves e can extend the current choices to some MST. With ties, it does not prove e appears in every MST. A deterministic tie rule may select one valid result, but the rule is a presentation decision rather than a mathematical uniqueness proof.
The respecting-cut condition matters. “Pick the globally cheapest unused edge” is incomplete: an edge inside an already connected component may close a cycle. Explain which boundary makes the proposed addition safe.
Can you trace competing solutions on one graph?
Use this original four-vertex fixture. Each row is a distinct undirected edge:
| Edge | Weight |
|---|---|
| AB | 1 |
| BC | 1 |
| AC | 1 |
| CD | 2 |
| BD | 2 |
| AD | 4 |
A possible Kruskal trace accepts AB and BC, skips AC because it closes the triangle, then accepts CD. The total is 4. A different tie order accepts AC and BC, then BD, also totaling 4.
There are six optimal trees: choose any two of the three weight-one triangle edges, then either CD or BD. All six connect the four vertices with three edges. Selecting AD instead raises the total to 6 when paired with two triangle edges.
You can establish the lower bound without relying on either algorithm's output. D needs an incident selected edge of weight at least 2. Every other selected edge has weight at least 1. A three-edge tree therefore costs at least 4, and the listed constructions attain that bound.
Our original local enumeration confirms six weight-four optima. Comparing exact sorted edge IDs would wrongly reject five of them unless the task explicitly required a shared tie-breaking rule. Compare coverage, acyclicity and objective value first.
How do Kruskal and Prim make different safe choices?
Reference fact: Princeton's Kruskal implementation sorts edges by weight and uses Union-Find to reject additions whose endpoints already share a component. It also supports forests, negative weights and ties. Kruskal implementation
For our fixture, Union-Find tracks the components created by accepted edges. Before adding CD, the partition is {A,B,C}, {D}. CD crosses that boundary. AC does not, even though it is cheaper. Union-Find answers the cycle question efficiently; the sorted edge order supplies the weight-based choice.
Reference fact: Princeton's eager Prim implementation maintains the cheapest connection from the current tree to each outside vertex using an indexed heap. Its documented bound is O(E log V) time and O(V) extra space, excluding the graph. Eager Prim implementation
If Prim starts at A, its next choice can be AB or AC. After reaching a second triangle vertex, a weight-one edge can reach the remaining triangle vertex. A weight-two edge then connects D. The intermediate priority values are edge-connection costs, not accumulated path distances from A.
Reference fact: lazy Prim retains candidate edges in a heap and discards entries whose endpoints are already in the tree. Princeton documents O(E log E) worst-case time and O(E) auxiliary space for that implementation. Lazy Prim implementation
These bounds describe particular implementations. A dense adjacency-matrix version can use vertex scans instead of a heap. In an interview, match the explanation to your actual data structures, including input scanning and initialization costs.
How can you certify a proposed tree independently?
Begin with structure. Verify that each selected edge exists with its original weight and identity, that the result covers the required vertices, and that it has no cycles. A plausible sum does not establish any of those properties.
Princeton's Kruskal code includes a checker that examines spanning, acyclicity and cut optimality. Implementation's validation logic Our original check uses an equivalent exchange question for every unselected, non-loop edge e: is e lighter than the heaviest edge on the tree path between its endpoints?
If it is, add e and remove that heavier path edge. You have constructed a cheaper spanning tree, which refutes optimality. If all such comparisons pass after the structural checks, no improving exchange exists; the candidate satisfies the MST optimality condition.
For T = {AB,BC,CD}, edge AC has weight 1 and the A-to-C tree path has maximum weight 1. The exchange is neutral and produces another optimum. BD similarly ties the maximum weight 2 on its tree path. AD has weight 4, exceeding the path maximum 2, so inserting it cannot improve this tree.
Now check the bad proposal {AB,BC,AD}. Its C-to-D path contains AD of weight 4. Unselected CD costs 2. Replacing AD with CD lowers total 6 to 4. This counterexample is easier to assess than “my implementation returned something different.”
For a connected graph, strict inequality between every non-tree edge and its path maximum establishes uniqueness. Equality identifies an alternative tree. The familiar condition “all weights distinct” is sufficient for uniqueness, but not necessary: AB=1, BC=1 and AC=3 still have one optimal edge set.
What do negative weights, loops and parallel edges change?
Negative weights are permitted by the documented Princeton MST implementations. Our original negative-weight fixture uses AB=−2, BC=0 and AC=5; the optimal tree costs −2. The algorithm compares edge weights and excludes cycles. It is not relying on a nonnegative-distance invariant.
Do not generalize this to selecting every negative edge. A negative self-loop cannot enter a spanning tree. A cycle of negative edges still violates the tree contract, even if adding it would reduce the sum of a more general connected subgraph.
Parallel edges need distinct identities when the output must name exact records. Between the same two endpoints, weight-one and weight-two edges are separate candidates; selecting both would form a cycle in an undirected multigraph. A map keyed only by endpoint pair can silently discard required input information.
For an original forest case, vertices A,B share edges of weights 1 and 2, C,D share an edge of weight 3, and isolated E has only a self-loop of weight −10. The forest chooses AB at 1 and CD at 3. E remains an isolated vertex. There are three components, two selected edges and total 4.
Official library boundary: NetworkX's MST API accepts undirected graphs, returns a forest when disconnected, and defaults a missing weight attribute to 1 for its Kruskal and Prim choices. It normally rejects NaN weights unless instructed to ignore them. NetworkX MST API
Specify your own contract instead of inheriting surprising defaults. Decide how missing or non-finite weights are handled and use arithmetic that cannot silently overflow the required total. The fixtures here use exact Python integers; they do not test floating-point tolerance choices.
What did the executable checks verify?
Our original Python Kruskal and lazy Prim implementations agree with independent enumeration of spanning subsets on the worked fixtures and 200 seeded five-vertex multigraphs. The generated inputs include ties, negative weights, loops, parallel edges and disconnected vertices.
The enumeration computes original connected components by traversal, considers subsets with V−c edges, and retains those preserving the same component partition. It then finds the smallest sum. That provides a different correctness path from trusting the same greedy selection twice.
The checks confirm six optima in the four-node graph, reject the weight-six proposal through the path certificate, and reproduce the forest and negative-weight totals. They also confirm the equal-weight triangle with a unique optimum. The linked Java and NetworkX implementations were researched, not executed locally.
Finite regression checks complement the cut proof; they do not replace it. During a timed interview, prioritize a tie case, a disconnected case and a competing proposal that looks connected but costs too much. Explain what each check could falsify rather than listing inputs without expected outcomes.
Practice connectivity and add the weight argument
The MST follow-ups below are original extensions, not claims that the records themselves describe dedicated MST interviews.
| Question | MST follow-up |
|---|---|
| Implement Union-Find for connectivity | Reject cycle edges while processing weights |
| Implement Union-Find and track components | Verify V−c selected edges for a forest |
| Implement Random Connectivity and Grid Routing | Separate network cost from route distance |
| Fewest Edge Relocations to Make an Undirected Graph Connected | State how existing connectivity affects edge eligibility |
| Find Earliest Fully Connected Time | Compare ordering by time with ordering by weight |
Return to the Union-Find exercise. Present one respecting cut, two different optimal trees and one cheaper exchange that disproves a competing proposal.