Minimum spanning trees: cuts, cycles, Prim and Kruskal
Contract and connection
Use the existing graph-representation, BFS/DFS and heap foundations. This lesson considers finite undirected weighted graphs without self-loops. Parallel edges may be treated as separate candidate edges. A spanning tree of a connected graph connects every vertex with no cycle, so it has V−1 edges. An MST minimizes total edge weight, not distances from a source. Weights may be negative, zero or tied.
1. Cuts and safe edges
A cut partitions vertices into nonempty S and V\S. An edge crosses it if its endpoints lie on opposite sides. Suppose a partial forest F is contained in some MST and no edge of F crosses a chosen cut; the cut respects F. Any minimum-weight crossing edge e is safe: some MST contains F together with e.
Proof: take an MST T containing F. If e is absent, add it to T, creating one cycle. The path between e's endpoints must cross the cut, so that cycle contains another crossing edge f. Because the cut respects F, f is not in F. Since e is a lightest crossing edge, w(e)<=w(f). Remove f. The result is a spanning tree no heavier than T, hence also an MST, and it includes F and e. Ties permit different MSTs; a lightest edge need not appear in every MST. A unique minimum crossing edge does appear in every MST, by the same exchange with strict improvement.
2. Cycle property and ties
A uniquely heaviest edge on a cycle belongs to no MST: deleting it after adding an alternative connection gives a strict improvement if a tree used it. If several edges tie for maximum, any one selected maximum can be excluded from some MST, but do not say all maximum edges must be absent from every MST. In a triangle with all weights 1, any two edges form an MST of weight 2. Tied weights do not necessarily imply multiple MSTs: an already-connected tree has only one spanning tree even if its edges tie.
3. Kruskal builds a forest
Sort all edges by nondecreasing weight. Start with each vertex as its own component. For edge (u,v), add it exactly when u and v currently belong to different components, then union those components. Disjoint-set union (DSU) supports the component tests; it is not a directed-graph reachability test. Accepted edges never form a cycle. The edge is safe across an appropriate current-component cut, so the growing forest remains extendable to an MST.
Example edges AB=1, BC=2, AC=3, CD=4, BD=5. Kruskal accepts AB,BC, rejects AC because it closes triangle ABC, accepts CD. Total 7; three edges span four vertices. Comparison sorting costs O(E log(E+1)); DSU initialization and operations add O(V+E α(V)) with path compression and union by rank, where α is the inverse Ackermann function. Retain the V initialization term for disconnected graphs with isolated vertices. For connected simple graphs this is commonly simplified to O(E log V).
4. Prim grows one tree
Start any vertex r. For each vertex outside the tree maintain key[v], the least weight of an edge connecting it to the tree, plus its parent. Initially key[r]=0 and other keys=∞. Extract the smallest-key vertex, add its parent edge if any, and update neighboring outside vertices when a cheaper connecting edge is found. This chooses a minimum edge across the current tree cut. Unlike Dijkstra, the update uses w(u,v), not a cumulative distance.
On the example, start A: choose AB=1, then BC=2, then CD=4; total 7. With an adjacency matrix and linear extract-min, time O(V²); adjacency lists plus an indexed binary heap give O((V+E) log V), often O(E log V) for connected graphs with V>=2. These bounds depend on representation.
5. Disconnected graphs and pitfalls
A disconnected graph has no spanning tree covering every vertex. Kruskal naturally returns a minimum spanning forest. Prim from one root reaches only that component; when the minimum remaining key is ∞, stop that component, then restart at an unvisited vertex with a new root key 0 to obtain a forest. A graph with c components yields V−c forest edges, including isolated vertices as one-vertex components. Negative edges are valid for both MST algorithms. Do not impose Dijkstra's nonnegative-weight condition on MSTs, and do not confuse a shortest-path tree with a minimum-total-weight tree.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Connected graph with 8 vertices: spanning-tree edges?
A. 6 B. 7 C. 8 D. 28
Answer: B
A: This would not connect all eight as a tree.
B: V−1=7.
C: Eight would create a cycle if connected.
D: 28 counts all possible simple undirected edges.
P02. A unique minimum crossing edge of a cut belongs to:
A. No MST B. Every MST C. Only graphs with positive weights D. Every possible spanning tree
Answer: B
A: The cut exchange forces inclusion.
B: Excluding it would permit a strictly cheaper exchange.
C: Negative weights do not invalidate the proof.
D: Nonminimum spanning trees may omit it.
P03. All-1 triangle: how many edges does any MST select?
A. 0 B. 1 C. 2 D. 3
Answer: C
A: No vertices are connected.
B: One edge leaves a vertex separate.
C: Any two connect all vertices without a cycle.
D: All three form a cycle.
P04. Kruskal on AB=1,BC=2,AC=3,CD=4,BD=5 has total MST weight:
A. 6 B. 7 C. 8 D. 15
Answer: B
A: The three lightest edges form a cycle and omit D.
B: AB+BC+CD=1+2+4=7.
C: A heavier valid tree is not optimal.
D: This sums every edge.
P05. Prim updates key[v] using:
A. key[u]+w(u,v) B. w(u,v) for a cheaper connecting edge C. Number of visited vertices D. BFS level only
Answer: B
A: That is cumulative-distance-style reasoning, not Prim.
B: The key is cheapest edge into the current tree.
C: Vertex count does not compare edge costs.
D: Weighted MST needs edge weights.
P06. Graph with V=9 and c=3 connected components: spanning-forest edges?
A. 3 B. 6 C. 8 D. 9
Answer: B
A: This is component count.
B: V−c=6.
C: V−1 applies only when connected.
D: A forest cannot have that many edges here.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Algorithms syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in