Minimum Spanning Trees: Kruskal, Prim, Cut Property, and Worked Examples for GATE CS

Minimum spanning tree questions look like free marks: sort edges and choose cheap ones. Yet cycle rejections, uniqueness twists, and shortest-path confusion cost students those marks. The six-vertex graph has a unique MST of weight 18; a second graph has two minimum trees of weight 6, exposing the traps around ties, shortest paths, and edge selection.

What a minimum spanning tree actually is

A spanning tree of a connected, undirected, weighted graph touches all V vertices with exactly V - 1 edges and no cycle. A minimum spanning tree, or MST, is the spanning tree with the least total weight. A disconnected graph has no spanning tree, only a spanning forest with one tree per component.

Three structural facts drive almost every MST question:

1. A spanning tree always has exactly V - 1 edges.

2. Removing any tree edge splits the tree into two components.

3. Adding any non-tree edge creates exactly one cycle.

These facts make greedy choices safe. MSTs minimise cable or pipeline used to connect sites. They support cluster analysis by linking nearby points, and give approximation algorithms a low-cost structure to build on.

The cut and cycle properties that make greedy correct

A cut partitions vertices into two non-empty sets. A minimum-weight edge crossing any cut belongs to some MST. If it is the unique minimum crossing edge, it belongs to every MST. This is the safe-edge rule behind both algorithms.

The cycle property is the mirror image: a cycle's unique maximum-weight edge belongs to no MST. The cut property brings safe edges in; the cycle property keeps edges out.

If all edge weights are distinct, the MST is unique. Equal weights are necessary for multiple MSTs, but a tie alone does not guarantee multiple answers.

For a compact five-vertex construction and weight-change drills, use Minimum Spanning Tree for GATE: Kruskal and Prim Numericals with Unique-MST Questions. The six-vertex graph below demands a different audit: certify every acceptance or rejection, then carry the same properties into tied-MST counts, bottleneck trees, and shortest-path traps.

Kruskal's algorithm with cut and cycle certificates

Take vertices {P, Q, R, S, T, U} and nine undirected edges: S-T = 1, Q-R = 2, P-R = 3, P-Q = 4, Q-S = 5, R-S = 6, T-U = 7, R-T = 8, and S-U = 9. Distinct weights make its MST unique.

Kruskal sorts all edges in ascending order, then accepts an edge only when it joins two different components.

Each accepted edge also has a cut certificate. S-T is uniquely lightest across {T}; Q-R across {Q}; P-R across {P}; Q-S across {P, Q, R}; and T-U across {U}. The rejected P-Q and R-S edges are uniquely heaviest on the cycles P-R-Q-P and R-Q-S-R. These certificates prove optimality edge by edge instead of relying only on the final total.

We now have V - 1 = 5 accepted edges, so we stop. The MST is {S-T, Q-R, P-R, Q-S, T-U}, with total weight:

1 + 2 + 3 + 5 + 7 = 18

Kruskal uses disjoint-set, or union-find, with union by rank and path compression for nearly constant-time cycle checks. Sorting dominates, giving O(E log E), also O(E log V) for a connected graph because V - 1 <= E <= V squared.

Prim's algorithm as a frontier audit on the same graph

Prim grows one tree outward. Starting at P, its trace on the same graph is:

1. Tree {P}: choose P-R (3).

2. Tree {P, R}: choose Q-R (2).

3. Tree {P, Q, R}: P-Q (4) now connects two tree vertices, so ignore it. Choose Q-S (5).

4. Tree {P, Q, R, S}: choose S-T (1).

5. Tree {P, Q, R, S, T}: choose T-U (7), which beats S-U (9).

Prim selects 3, 2, 5, 1, 7, but produces the same five edges and total 18. Kruskal grows a forest globally with union-find. Prim grows one tree using a priority queue of frontier edges. A binary heap gives Prim O(E log V); an adjacency matrix gives O(V squared), often better on dense graphs. Kruskal costs O(E log E).

The start vertex changes discovery order, not the minimum total. With distinct weights it cannot change the unique edge set. With ties, different starts may return different valid MSTs of equal weight.

MST counting and uniqueness: the NAT pattern

Take {X, Y, Z, W} with X-Y = 1, X-Z = 2, Y-Z = 2, and Z-W = 3. Z-W is the only edge touching W, so it is forced. X-Y is the unique lightest edge across the cut separating X, so it is also forced.

Connect Z by choosing exactly one of X-Z and Y-Z. Either works, so there are 2 distinct MSTs, each weighing:

1 + 2 + 3 = 6

For counting, fix forced edges such as unique cut minima and bridges. Then count tied-edge combinations that connect every vertex without cycles. Independent choices multiply, but ties in one cycle interact.

Keep these MSQ facts ready:

• Adding the same constant to every edge leaves the MST unchanged because each tree has V - 1 edges. Shortest paths can change because paths have different edge counts.

• The maximum-weight edge of a graph can belong to the MST when it is a bridge.

• A minimum-weight edge belongs to some MST. With distinct weights, it belongs to the unique MST.

Traps that turn easy MST marks into negative marks

MST is not Dijkstra's shortest-path tree. Both are greedy and often taught together, but MST minimises total tree weight while Dijkstra minimises each distance from one source. Here the MST path P to T weighs 3 + 2 + 5 + 1 = 11, while P-Q-S-T weighs 4 + 5 + 1 = 10. Write down what is being minimised.

Negative edges do not break Kruskal or Prim. Students transfer Dijkstra's restriction, but MST properties do not require non-negative weights. An MST is also a minimum bottleneck spanning tree: it minimises the largest chosen edge. The converse fails because a bottleneck tree need not minimise total weight.

Complexity follows the implementation. Claiming O(E log E) while checking each edge with a fresh traversal is inconsistent; naive checks can approach O(EV). Use union-find, and never claim uniqueness without checking weights or proving it.

How GATE and interviews test minimum spanning trees

The official GATE 2027 CS syllabus lists minimum spanning trees under Algorithms. Questions ask for an MST weight such as 18, an MST count such as 2, forced or forbidden edges, true-or-false property sets, or Prim's order from a fixed start.

Interviews ask you to choose Kruskal or Prim for a graph's density, explain union-find plainly, separate low-cost cabling from low-latency routing, or justify the cut property through an exchange argument. Revise heaps and union-find through the Algorithms coverage in Zero to Hero: Complete CS Course, then test the same decisions under time pressure in the GATE Test Series: Mocks & Topic-wise Tests.

MST summary and revision plan

A spanning tree has V - 1 edges and no cycle; an MST is the cheapest one. Cut brings edges in, cycle keeps edges out. Kruskal uses union-find; Prim uses a heap. Distinct weights give one MST, while ties create counting choices. MST is not shortest path.

Use the GATE CS Exam Preparation category to choose the next subject drill. Before moving on, rerun Prim from U and verify that only the discovery order changes; the unique edge set and total weight 18 must remain fixed.