Questions: Minimum Spanning Trees and Optimization

Question 1

A network engineer connects 5 cities by always adding the cheapest remaining cable that does not create a loop. She never considers the global structure. Yet this greedy strategy is guaranteed to find the optimal network. What property makes this provably correct?

• A. The MST is unique when all edge weights are distinct, so any consistent rule finds it.
• B. The cut property: the minimum-weight edge crossing any partition of vertices must belong to every MST.
• C. Greedy algorithms always produce optimal results for graph problems.
• D. Trees have exactly n−1 edges, so any set of n−1 acyclic edges forms a valid MST.

Answer: (B)

The cut property is the key theoretical underpinning: given any partition of the graph's vertices into two groups, the minimum-weight edge crossing that cut belongs to every MST (assuming distinct weights). This means each greedy choice — 'take the cheapest edge that does not form a cycle' — adds an edge that must be in the MST regardless of future choices. Without this property, locally cheap choices could force globally expensive ones. Option D is wrong: n−1 arbitrary acyclic edges can fail to span the graph, and spanning n−1 edges that are individually cheap may not minimize total weight.

Question 2

What is the key difference in approach between Kruskal's algorithm and Prim's algorithm?

• A. Kruskal's guarantees an MST; Prim's only finds a locally optimal spanning tree.
• B. Kruskal's processes all edges globally in sorted order; Prim's grows a single tree vertex by vertex from a starting node.
• C. Kruskal's works only on undirected graphs; Prim's works on directed graphs.
• D. Kruskal's uses a priority queue for edge selection; Prim's uses union-find for cycle detection.

Answer: (B)

Both algorithms are correct and both produce MSTs. Kruskal's is edge-focused: sort all edges by weight, then greedily add each if it connects two previously disconnected components (using union-find to detect cycles). Prim's is vertex-focused: grow a single tree from a starting vertex by repeatedly adding the cheapest edge connecting the current tree to any unincluded vertex. Option D reverses the data structures — Prim's typically uses a priority queue to find the minimum adjacent edge efficiently, while Kruskal's uses union-find for cycle detection.

Question 3

If a connected weighted graph has all distinct edge weights, it has exactly one minimum spanning tree.

• T. True
• F. False

Answer: True

With all distinct edge weights, the cut property uniquely determines each MST edge: for any cut, there is exactly one minimum-weight crossing edge, so every MST must include it. Both Kruskal's and Prim's will make identical edge choices and converge on the same unique MST. If two edges tie in weight, different algorithms might choose either, potentially producing different (but equally valid) MSTs. Distinctness eliminates all ties and forces uniqueness.

Question 4

Kruskal's algorithm finds the MST by starting with the complete graph and repeatedly removing the most expensive edge that does not disconnect the graph.

• T. True
• F. False

Answer: False

This describes a valid but different method (reverse-delete). Kruskal's actually starts with all vertices isolated (no edges) and adds edges in increasing weight order, skipping any that would form a cycle. The approach grows from an empty forest toward a connected tree. The key operation is cycle detection via union-find when adding edges, not connectivity checking when removing them. Both methods produce the same MST, but Kruskal's is additive, not subtractive.

Question 5

Why does the cut property guarantee that a greedy edge-selection strategy produces a globally optimal spanning tree rather than just a locally cheap one?

Model answer: The cut property states that for any partition of vertices into two groups, the minimum-weight edge crossing that cut must belong to every MST. This means each greedy choice to include the cheapest safe edge is not just locally convenient — it is logically required by global optimality. Any spanning tree that excludes this edge would have to include a heavier crossing edge instead, making it non-minimal. Because this reasoning applies at every step, each greedy decision is permanently correct, and the accumulated choices must form the globally optimal MST.

This is what distinguishes MST from problems where greedy fails (like the 0/1 knapsack). The cut property creates a 'safe' choice at every stage — not just a heuristic. The underlying reason is that spanning trees form a matroid, a combinatorial structure where the greedy algorithm is always exactly optimal. The cut property is the matroid exchange property expressed in graph-theoretic terms.