Self-Assessment Quiz: Spanning Trees, MSTs, and Network Design

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Question 1

A connected graph has $n$ vertices. Every spanning tree of it has exactly how many edges?

A) $n$ B) $n-1$ C) $n+1$ D) it depends on the number of edges in the graph

Question 2

A minimum spanning tree of a connected weighted graph is:

A) the spanning tree containing the single cheapest edge B) a spanning tree whose total edge weight is minimum among all spanning trees C) the tree formed by the shortest paths from one source vertex D) any tree that touches every vertex

Question 3

In Kruskal's algorithm, an edge $(u,v)$ is added to the forest if and only if:

A) it is the next edge in ascending weight order B) find(u) == find(v) C) find(u) != find(v) (its endpoints are in different components) D) it has weight less than the average edge weight

Question 4

The data structure Kruskal's algorithm uses to test "do these two endpoints already connect?" is:

A) a priority queue (heap) B) a stack C) union-find (disjoint-set forest) D) a hash table of paths

Question 5

Prim's algorithm, at each step, adds:

A) the globally cheapest unused edge B) the cheapest edge crossing from the in-tree set to the not-yet-in-tree set C) the cheapest edge incident to the start vertex D) any edge that does not form a cycle

Question 6

The two optimizations that make union-find nearly constant-time per operation are:

A) sorting and binary search B) path compression and union by rank C) memoization and tail recursion D) hashing and rehashing

Question 7

Both Kruskal and Prim run in $O(E \log V)$ time (with a binary heap for Prim). For Kruskal, the term that dominates this bound is:

A) the union-find operations B) sorting the edges C) checking connectivity at the end D) building the adjacency list

Question 8

A light edge crossing a cut $(S, V \setminus S)$ is:

A) the lowest-degree crossing edge B) the minimum-weight edge among all edges crossing the cut C) any edge with both endpoints in $S$ D) the edge added most recently to the tree

Question 9

The cut property states that a light edge crossing any cut belongs to:

A) no MST B) every MST, always C) some MST D) exactly two MSTs

Question 10

The proof technique used to establish the cut property is:

A) induction on the number of edges B) an exchange (swap) argument C) proof by cases on vertex degree D) the pigeonhole principle

Question 11

The cycle property states that the unique heaviest edge on any cycle is in:

A) some MST B) every MST C) no MST D) exactly one MST

Question 12

When all edge weights in a connected graph are distinct, the MST is:

A) not guaranteed to exist B) unique C) always a path D) the same as the shortest-path tree

Question 13

Adding one non-tree edge to a spanning tree creates exactly how many cycles?

A) zero B) exactly one C) exactly two D) it depends on the graph

Question 14 (True/False, justify)

True or false: The path the MST provides between two vertices is always the shortest path between them in the original graph. Justify in one sentence.

Question 15 (True/False, justify)

True or false: If you run Prim's algorithm from two different starting vertices on a graph with distinct edge weights, you may get two trees of different total weight. Justify in one sentence.

Question 16 (True/False, justify)

True or false: On a disconnected graph, Kruskal's algorithm (without modification) returns a single spanning tree. Justify in one sentence.

Question 17

You have $50$ towns and want to connect them with the least total cable length, with no concern for hop count or fault tolerance. The right tool is:

A) Dijkstra's shortest-path algorithm B) a minimum spanning tree algorithm C) breadth-first search D) topological sort

Question 18 (Short answer)

After building the MST of a data set (edge weight = distance), how do you split the data into exactly $k$ single-linkage clusters?

Question 19 (Short answer)

Name the one substantive difference between Prim's algorithm and Dijkstra's algorithm in terms of what each stores as a frontier vertex's priority-queue key.

Question 20 (Short answer)

Give one concrete reason a real network designer would deliberately add edges beyond those in the MST.

Answer Key

Q Ans Note
1 B A spanning tree is a tree on $n$ vertices, so it has $n-1$ edges (Ch. 31).
2 B MST minimizes total edge weight over all spanning trees.
3 C Add iff endpoints are in different components (no cycle).
4 C Union-find answers "already connected?" in near-constant time.
5 B Prim takes the cheapest edge crossing the current tree boundary (a cut).
6 B Path compression + union by rank give the $\alpha(n)$ bound.
7 B Sorting is $O(E\log V)$; union-find work is negligible by comparison.
8 B Light edge = minimum-weight crossing edge.
9 C Some MST (every MST if the light edge is unique).
10 B Exchange argument: swap the light edge into any MST without raising weight.
11 C The unique heaviest edge of a cycle is in no MST.
12 B Distinct weights force a unique MST.
13 B Exactly one cycle (the endpoints were already joined by a unique tree path).
14 False MST optimizes total weight, not per-pair distance; e.g. triangle $w(XY)=w(YZ)=1, w(XZ)=1.5$ gives tree distance $2 \ne 1.5$.
15 False Distinct weights ⇒ unique MST, so any correct algorithm from any start returns the same tree (same weight).
16 False On a disconnected graph it returns a minimum spanning forest (one MST per component).
17 B Minimum total connection cost with everything connected = MST.
18 — Delete the $k-1$ heaviest MST edges; the tree falls into $k$ components.
19 — Dijkstra keys by total distance from the source; Prim keys by the single cheapest edge to the current tree.
20 — Fault tolerance/redundancy: a tree has no alternate routes, so one link failure disconnects it.

Topics to review by question

Questions Topic
1, 13 Spanning-tree structure (edge count, one-cycle fact) — §32.1
2, 12, 17 The MST problem and what it optimizes — §32.2, §32.6
3, 4, 6, 7 Kruskal and union-find — §32.3
5, 19 Prim and its relation to Dijkstra — §32.4
8, 9, 10, 11 Cut and cycle properties (and the exchange argument) — §32.5
14, 16, 20 Boundaries: MST vs. shortest-path tree, forests, redundancy — §32.6
15 Uniqueness under distinct weights — §32.4, §32.5
18 Single-linkage clustering application — §32.6