3.5.14 · D5Graphs
Question bank — Minimum Spanning Tree — Kruskal's (Union-Find), Prim's (priority queue)
True or false — justify
TF. Every connected undirected graph has at least one spanning tree.
True. A connected graph can always be trimmed of cycle edges until exactly edges remain, still connecting all vertices — that is a spanning tree.
TF. A graph can have more than one distinct MST.
True. When two or more edges share the same weight, different choices can produce different trees — but every such tree has the same total weight.
TF. If all edge weights are distinct, the MST is unique.
True. With no ties, the cut property forces exactly one lightest crossing edge at every cut, so no choice is ever ambiguous.
TF. An MST always contains the single lightest edge of the whole graph.
True. Take the cut separating that edge's two endpoints from everything else — it is the lightest crossing edge of some cut, hence safe by the cut property.
TF. An MST always contains the single heaviest edge of the graph.
False. The heaviest edge is usually the top edge of some cycle, and the cycle property lets us delete it. It is included only if the graph would disconnect without it (e.g. a bridge).
TF. Kruskal's and Prim's may build different trees on the same graph.
True. They pick edges in different orders, so on tied weights they can diverge — but the total weight they reach is identical.
TF. MST algorithms require all weights to be positive.
False. Kruskal and Prim only sort and compare weights; they never add distances along paths, so negative or zero weights work fine.
TF. Multiplying every edge weight by a positive constant changes which edges the MST picks.
False. Scaling by a positive constant preserves the ordering of weights, and both algorithms depend only on ordering — the same edges are chosen.
TF. Adding the same constant to every edge weight can change the MST.
False for a fixed spanning tree count: every spanning tree has exactly edges, so each total rises by equally — the relative ranking, and thus the MST, is unchanged.
TF. MST is only defined for connected graphs.
True. A disconnected graph has no spanning tree; the correct object there is a minimum spanning forest (an MST per connected component).
TF. Prim's and Dijkstra's are the same algorithm with a different comparison key.
True in skeleton. Both grow from a seed using a min-heap; Prim keys on edge weight to the frontier, Dijkstra keys on accumulated path distance from the source.
Spot the error
Err. "Pick the globally cheapest edge every round and you get Kruskal's MST."
Wrong — Kruskal also rejects any edge whose endpoints are already connected (would form a cycle). Pure "cheapest globally" without the cycle check is not an MST algorithm.
Err. "In Prim's lazy heap, pushing a node that's already visited is a bug I must prevent."
Not a bug. Stale entries are simply skipped with
if visited[u]: continue when popped — this lazy deletion is the standard, correct design.Err. "Kruskal and Prim also work on directed graphs."
MST is defined only for undirected graphs. The directed version is the minimum arborescence (Chu–Liu/Edmonds), a genuinely different algorithm.
Err. "Union-Find's find should search the tree for the smaller-numbered vertex."
No.
find follows parent pointers to the root (the set representative); vertex numbers are irrelevant to which root a set has.Err. "I stop Kruskal only when I run out of edges."
Inefficient/wrong intent — stop as soon as you have accepted edges, because a tree on vertices needs exactly that many. Continuing wastes work.
Err. "Dijkstra's negative-weight failure means Prim also fails on negatives."
False transfer. Dijkstra fails because it relaxes along paths; Prim never sums along a path, so negatives are harmless to it.
Err. "The cut property lets me pick any crossing edge safely."
Only the minimum-weight crossing edge is guaranteed safe. A heavier crossing edge may not lie in any MST.
Err. "Path compression in Union-Find changes which set a node belongs to."
No. It only re-points nodes closer to the same root to speed future lookups; every node's set membership is unchanged.
Why questions
Why. Why can a cycle never appear in an MST?
Any cycle has a heaviest edge you can delete while staying connected (cycle property), so keeping it only wastes weight — an MST never needs it.
Why. Why does Kruskal sort edges ascending rather than descending?
Greedy correctness: processing lightest first means the first edge that joins two separate components is the lightest crossing edge of the cut between them, which the cut property certifies as safe.
Why. Why does Prim use a min-heap instead of scanning all frontier edges each step?
The heap returns the globally cheapest crossing edge in , avoiding an scan per step and giving the bound. See Priority Queue (Binary Heap).
Why. Why do both algorithms reach the same total weight even if the trees differ?
Both only ever add safe crossing edges justified by the cut property, and the minimum total is an invariant of the graph — the tree shape can vary, the cost cannot.
Why. Why is Union-Find (not a plain visited array) the natural cycle-check for Kruskal?
The question is "are these two endpoints already in the same connected group?" DSU answers exactly that — dynamic same-component queries — in near-constant amortized time.
Why. Why is Kruskal preferred for sparse graphs and Prim (heap) often for dense ones?
Kruskal is edge-centric at , ideal when is small and you already hold an edge list; Prim is vertex-centric and stays , comfortable with adjacency lists on dense graphs. See Graph Representations.
Why. Why is "greedy" trustworthy here when it fails for many other problems?
Because the exchange argument (swap in the lighter crossing edge, never increase cost) proves each greedy choice is safe — a structure most greedy problems lack. See Greedy Algorithms.
Edge cases
Edge. What is the MST of a single vertex with no edges?
The empty edge set. A tree on vertex needs edges and has weight .
Edge. What if the graph is already a tree?
It is its own MST — a tree has no cycles and exactly edges, so nothing can be removed or improved.
Edge. What happens if you run Kruskal on a disconnected graph?
It runs out of safe edges before reaching ; you end with a spanning forest — one MST per component — not a single spanning tree.
Edge. Two edges have identical weight and both close a cut. Which does Kruskal take?
Whichever appears first in the sorted order; either is safe, and both lead to a valid (possibly different) MST of equal total weight.
Edge. A parallel edge (two edges between the same pair) exists. What does the MST do?
It can use at most the cheaper of the two; the heavier parallel edge would form a 2-vertex cycle and is discarded.
Edge. A self-loop (edge from a vertex to itself) exists. Is it ever in an MST?
Never — its two endpoints are the same vertex, so it is instantly a cycle and adds no connectivity.
Edge. Every edge weight is zero. What is the MST weight?
Zero, with any spanning tree valid. The algorithms still correctly avoid cycles and stop at edges.
Recall One-line self-test before you leave
Ask: "Does my rule survive ties, negatives, zeros, disconnection, self-loops, and directedness?" If any case breaks it, you found the trap. ::: If unsure, re-derive from the cut property — it is the single fact behind every correct answer above.