Exercises: Spanning Trees, Minimum Spanning Trees, and Network Design

These run from mechanical traces of Kruskal and Prim up through full correctness proofs, code, and network-design modeling. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the daggered (†) and odd-numbered problems are in the appendix answers-to-selected.md — trace or prove each one yourself before you peek. Several problems reuse the chapter's running office graph:

          A
        2/ \3
        /   \
       B--1--C
       |     |
      4|     |5
       |     |
       D--6--E

with $w(AB)=2,\ w(AC)=3,\ w(BC)=1,\ w(BD)=4,\ w(CE)=5,\ w(DE)=6$.

Part A — Warm-ups (⭐)

32.1 † A connected graph has $20$ vertices and $50$ edges. (a) How many edges does any spanning tree of it contain? (b) How many of the original edges are left out of a spanning tree? (c) If you add one of those left-out edges back to a spanning tree, how many cycles does the result contain?

32.2 State, in your own words, the difference between what Kruskal's local choice optimizes and what Prim's local choice optimizes. One sentence each.

32.3 † For the office graph, compute the total weight of each of these three spanning trees and say which (if any) is a minimum spanning tree: (a) $\{AB, AC, BD, CE\}$; (b) $\{BC, AB, BD, CE\}$; (c) $\{BC, AC, BD, CE\}$.

32.4 True or false, with a one-line reason each: (a) every connected graph has at least one spanning tree; (b) a graph can have two different spanning trees of equal weight; (c) removing any one edge from a spanning tree disconnects it.

32.5 † Consider the cut $S = \{A, D\}$ versus $V \setminus S = \{B, C, E\}$ of the office graph. List every crossing edge with its weight, and identify the light edge of this cut.

Part B — Ordinary computation (⭐⭐)

32.6 † Run Kruskal's algorithm by hand on the graph below, showing your work as a table with columns edge, weight, endpoints' components, add or skip. Report the MST and its total weight.

   vertices: P Q R S T
   edges (weight): PQ=4, PR=1, QR=2, QS=7, RS=5, RT=3, ST=6

32.7 Run Prim's algorithm by hand on the same graph as 32.6, starting at vertex $P$. Show the crossing edges considered at each step, and confirm you get the same total weight as 32.6.

32.8 † A graph has edge weights $1, 2, 3, 4, 5, 6, 7$ on seven distinct edges among five vertices. Without seeing the graph, what is the largest number of those edges that could possibly appear in an MST, and the smallest? Explain.

32.9 Trace the union-find structure (parent pointers, with path compression as in §32.3) through the following operation sequence on elements $\{0,1,2,3,4\}$, each starting as its own set: union(0,1), union(2,3), union(1,2), find(3), find(0). After the two find calls, write the parent array. (Use the convention from the chapter's Python: union(x,y) sets parent[find(x)] = find(y).)

32.10 † For the office graph, use the cycle property to identify every edge that is in no MST. Justify each with the specific cycle in which it is the unique heaviest edge.

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. Reference implementations live in code/exercise-solutions.py.

32.11 † Write tree_weight(mst_edges) that takes a list of (u, v, w) triples and returns the total weight $\sum w$. Then call it on the office-graph MST [(1,2,1),(0,1,2),(1,3,4),(2,4,5)] and show the expected output.

32.12 Write is_spanning_tree(n, tree_edges) that returns True iff the given edge set is a spanning tree of an $n$-vertex graph: it must have exactly $n-1$ edges, connect all $n$ vertices, and be acyclic. (Hint: $n-1$ edges plus "connected" already forces acyclic — you may check connectivity with a union-find or BFS.) Test it on the office-graph MST (should be True) and on [(0,1,2),(0,2,3),(1,2,1),(1,3,4)] (should be False — why?).

32.13 † Modify the chapter's kruskal(n, edges) into kruskal_forest(n, edges) that does not assume the graph is connected: it should return the minimum spanning forest (one MST per connected component) as (forest_edges, total_weight, num_components). Test it on a graph with two components: edges = [(1,0,1),(2,2,3)] over $n=4$ vertices.

32.14 Write count_mst_edges_used(n, edges) that runs Kruskal and returns how many edges were skipped (rejected as cycle-forming) before the spanning tree was complete. Test it on the office graph; the expected answer should match your hand-trace in §32.3.

Part D — Find the error (⭐⭐)

Each argument below is flawed. State precisely which step fails and why; then give the correct statement.

32.15 † Claim: "In Kruskal's algorithm, sorting edges in descending order and adding each edge that does not form a cycle also produces a minimum spanning tree." "Proof": it is greedy and avoids cycles, just like ascending Kruskal, and any greedy cycle-avoiding method gives an MST. — Find the flaw. (Hint: hand-run descending-order "add if no cycle" on the office graph and compare the total to $12$.)

32.16 Claim: "The MST contains the shortest path between every pair of vertices." "Proof": the MST is the cheapest tree, so the unique path it provides between any two vertices must be the cheapest route between them. — Find the flaw, and give the chapter's triangle counterexample explicitly.

32.17 † A student offers this proof of the cut property. "Let $e$ be a light edge crossing cut $(S, V\setminus S)$ and let $T$ be an MST not containing $e$. Add $e$ to $T$, creating a cycle. Remove any other edge $e'$ on that cycle. Then $T' = (T \setminus \{e'\}) \cup \{e\}$ is a spanning tree, and since $e$ is light, $w(T') \le w(T)$, so $T'$ is an MST containing $e$." — One step is not justified: removing any edge on the cycle. Identify the gap and state the precise condition $e'$ must satisfy for the weight comparison $w(e) \le w(e')$ to hold. (Hint: re-read §32.5 — which edge on the cycle is guaranteed to be a crossing edge?)

32.18 Claim: "Prim's algorithm starting from a different vertex can produce a spanning tree of different total weight." — Decide whether this is true or false. If false, explain the flaw in the reasoning that it might be true; if true, give an example. (Connect your answer to the cut property.)

Part E — Prove it (⭐⭐ / ⭐⭐⭐)

32.19 † (Scaffolded — fill in the missing steps.) Prove that if all edge weights of a connected graph $G$ are distinct, then $G$ has a unique MST. Fill the blanks.

  • Suppose, for contradiction, that $G$ has two distinct MSTs, $T_1$ and $T_2$. Since they differ, there is an edge in one but not the other; among all such edges, let $e$ be the one of $\underline{\hphantom{xxxxxxx}}$ (minimum / maximum) weight. Without loss of generality $e \in T_1$ and $e \notin T_2$.
  • Add $e$ to $T_2$. This creates exactly one cycle $C$ (because $\underline{\hphantom{xxxxxxxxxxxxx}}$).
  • Cycle $C$ must contain an edge $e'$ with $e' \notin T_1$ (otherwise $C \subseteq T_1$, but $\underline{\hphantom{xxxxxxxxxxxxx}}$). By the choice of $e$ as the minimum-weight differing edge, $w(e) \underline{\hphantom{xx}} w(e')$ (and the weights are distinct, so the inequality is strict).
  • Now form $T_2' = (T_2 \setminus \{e'\}) \cup \{e\}$, a spanning tree with $w(T_2') = w(T_2) - w(e') + w(e) \underline{\hphantom{xx}} w(T_2)$. This contradicts $\underline{\hphantom{xxxxxxxxxxxxx}}$. Hence the MST is unique. $\blacksquare$

32.20 Prove that every edge $e$ of a connected graph $G$ that is the unique cheapest edge incident to one of its endpoints belongs to every MST of $G$. (Hint: apply the cut property to a well-chosen cut.)

32.21 † Prove that a spanning tree $T$ of $G$ is a minimum spanning tree if and only if for every non-tree edge $e = (u,v)$, $e$ is a maximum-weight edge on the cycle that $e$ forms with the tree path between $u$ and $v$ (the cycle optimality condition). You may prove one direction in full and sketch the other. (This is the standard "no improving swap exists" characterization of an MST.)

32.22 (⭐⭐⭐, the minimax property.) Prove that in any MST $T$, the path between two vertices $u$ and $v$ is a minimax path: the maximum-weight edge on the $u$–$v$ path in $T$ is as small as possible among all $u$–$v$ paths in $G$. (Hint: suppose some other path had a smaller maximum edge; combine the cut property with the cycle property.) This is the "bottleneck" guarantee promised in §32.6.

Part F — Model it, Conjecture and test (⭐⭐⭐)

32.23 † (Model it.) A university wants to connect its $9$ buildings to a single fiber backbone for the least total trenching cost; it does not care about hop count or redundancy, and every pair of buildings has a known trenching cost. Translate this scenario into a precise discrete-math problem: name the mathematical object (vertices? edges? weights?), state exactly what is being optimized, name the algorithm you would run, and state in one sentence what you would tell the procurement committee about optimality and which property proves it. Then state one realistic objective for which an MST would be the wrong tool, and what you'd use instead.

32.24 (Model it.) You are given $200$ data points in the plane and want to split them into $5$ clusters using single-linkage clustering (§32.6). Describe the construction as a sequence of discrete-math operations: what graph do you build, what are the edge weights, what algorithm do you run, and what is the final step that produces exactly $5$ clusters? State the number of edges you delete.

32.25 † (Conjecture and test, then prove.) Let $G$ be a connected weighted graph. Conjecture a relationship between the number of edges Kruskal adds and the number of vertices $n$, and between the number of edges Kruskal examines (in the worst case) and the number of edges $E$. First test your conjecture in code by instrumenting kruskal to count adds and examinations on three small graphs you write out by hand. Then prove the relationship for the number of edges added.

32.26 (Conjecture and test.) Form a conjecture: "For a connected graph with distinct edge weights, Kruskal and Prim (from any start vertex) always return the identical edge set." Test it by implementing both and comparing their output (as sets) on five hand-written graphs with distinct weights, and on one graph with a tie. Report what changes when there is a tie, and connect your finding to the uniqueness result of Exercise 32.19.

Part G — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp. Pull only on tools you've already built.

32.27 † (Ch. 31 + 32.) A tree on $n$ vertices has $n-1$ edges (Chapter 31). Use this fact twice to prove that adding any single non-tree edge to a spanning tree creates exactly one cycle. (Hint: count edges before and after; a connected graph on $n$ vertices with $n$ edges has exactly one cycle.)

32.28 (Ch. 29 + 32.) Prim's algorithm and Dijkstra's algorithm (Chapter 29) share almost identical code. Write both priority-queue key update rules side by side — "when we relax an edge $(u,v)$ of weight $w$, the new key for $v$ is $\dots$" — and explain in one sentence why that single difference is exactly the difference between "cheapest tree" and "cheapest paths."

32.29 † (Ch. 6 + 32.) Prove by induction on the number of vertices added that the set $S$ of vertices in Prim's tree is always connected (within the chosen tree edges) throughout the algorithm. State $P(k)$ for "after $k$ vertices have been added," then give base case and inductive step.

32.30 (Ch. 15/16 + 32.) Cayley's formula (cited in §32.1) says the complete graph $K_n$ has $n^{n-2}$ spanning trees. (a) How many spanning trees does $K_4$ have? List enough structure to be convinced (you need not draw all of them). (b) Using a counting argument from Part III, explain why the number of spanning trees of any simple graph on $n$ vertices is at most $n^{n-2}$.

32.31 (Deep Dive — reverse-delete.) The reverse-delete algorithm sorts edges in descending weight and deletes each edge whenever its removal keeps the graph connected. Argue, using the cycle property, that reverse-delete produces an MST. Where in your argument do you use "removal keeps the graph connected"?

32.32 (Deep Dive — Borůvka.) Borůvka's algorithm (1926) repeats: each component simultaneously selects its own cheapest outgoing edge, and all selected edges are added at once. (a) Using the cut property, argue every edge Borůvka adds is safe. (b) Argue that the number of components is at least halved each round, so the algorithm finishes in $O(\log V)$ rounds. (Assume distinct weights so no two components pick the same edge in conflicting directions.)

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: a clearly identified cut or cycle, an explicit exchange (which edge swaps for which), a correct weight comparison, and a clean appeal to the cut or cycle property by name.