Kruskal's rule is simple: sort edges, take the cheapest one that does not close a cycle, and stop at n - 1 edges. Yet each step hides an exam trap. Attempt these 12 MCQs before reading the answers. Eight of them carry a named paper, from GATE 2003 through to TPSC 2026, and about 40 minimum spanning tree questions sit inside the Algorithms learn module.
What a minimum spanning tree actually is
A spanning tree keeps all n vertices, has n - 1 edges, and has no cycle. An MST minimises total connection cost, not a route between two vertices. It can therefore leave a long path between a given pair and still be the cheapest network overall. Minimum Spanning Tree for GATE: Kruskal and Prim Numericals builds one by both algorithms on a single five-vertex graph.
Q1. Primary application of an MST
What is the primary application of the Minimum Spanning Tree (MST)?
(a) Finding the shortest path in a graph
(b) Connecting all nodes with the least total edge weight
(c) Counting the number of cycles in a graph
(d) Finding the maximum path in a graph
Answer: (b). An MST minimises a connected network's total cost. Laying cable to every house is an MST problem; navigating from home to office is shortest path. The network may still have long routes between pairs.
Q2. Edge count of a spanning tree (BPSC 2024)
How many edges does a spanning tree of a graph with N vertices have?
(a) N
(b) N-1
(c) N(N-1)/2
(d) More than one of the above
(e) None of the above
Answer: (b). A tree has N - 1 edges. One fewer disconnects it; one more creates a cycle. N(N - 1)/2 counts a complete graph's edges. Reject any MST with a different count.
Kruskal's rule, named and classified
Sort all edges by non-decreasing weight. Add an edge only if its endpoints are in different components. Stop after n - 1 additions. This cheapest-safe choice is greedy.
Q3. Identify Kruskal's algorithm (IBPS 2025)
Which algorithm finds the Minimum Spanning Tree by selecting edges in increasing order of weight?
(a) Prim's Algorithm
(b) Dijkstra's Algorithm
(c) Kruskal's Algorithm
(d) Floyd-Warshall Algorithm
(e) Bellman-Ford Algorithm
Answer: (c). Increasing edge order identifies Kruskal. Prim grows one tree through its cheapest boundary edge. The other three solve shortest paths, not MSTs.
Q4. Match algorithms and paradigms (GATE 2017)
Consider the following table:
Algorithms | Design Paradigms |
|---|---|
P. Kruskal | i. Divide and Conquer |
Q. Quicksort | ii. Greedy |
R. Floyd-Warshall | iii. Dynamic Programming |
Match the algorithms to the design paradigms they are based on.
(a) P-ii, Q-iii, R-i
(b) P-iii, Q-i, R-ii
(c) P-ii, Q-i, R-iii
(d) P-i, Q-ii, R-iii
Answer: (c). Kruskal makes greedy safe-edge choices. Quicksort partitions and recurses, so it is divide and conquer. Floyd-Warshall tabulates subproblem answers, so it is dynamic programming.
Union-find and Kruskal's running time
Sorting gives the scan order. Disjoint Set Union, or union-find, compares the endpoints' roots. Equal roots mean that the edge closes a cycle.
Q5. Kruskal's primary data structure (TPSC 2026)
In Kruskal's algorithm for finding Minimum Spanning Tree, which data structure is primarily used?
(a) Queue
(b) Stack
(c) Disjoint Set Union
(d) Priority Queue only
Answer: (c). DSU performs the cycle test. Edge ordering cannot detect cycles. "Only" makes (d) false. Prim more naturally uses a priority queue.
Q6. Time complexity of Kruskal's algorithm
What is the time complexity of Kruskal's algorithm for finding the minimum spanning tree?
(a) O(n)
(b) O(log n)
(c) O(n^2)
(d) O(n log n)
Answer: (d). For m edges, sorting costs O(m log m) and dominates union-find. This is O(m log n) for a simple graph. Here n denotes input size, giving O(n log n).
MST properties that setters keep testing
Distinct weights force a unique MST. A transformation that shifts every tree total equally also preserves the MST.
Q7. Distinct weights and uniqueness
In a connected weighted graph, every edge has a distinct weight. How many unique MSTs can such a graph have?
(a) One
(b) Two
(c) Zero
(d) More than two
Answer: (a). No ties force every safe choice. Exchanging a chosen cut edge uses a heavier one. Repeated weights need not create multiple MSTs.
Q8. Weight transformation and the cheapest edge
Which of the following statement(s) is/are correct?
(i). If each edge weight is increased by 1, the minimum spanning tree doesn't change
(ii). If the minimum cost edge e of a graph is unique, then this edge is included in any MST.
(a) Only (i)
(b) Only (ii)
(c) Both (i) and (ii)
(d) Neither (i) nor (ii)
Answer: (c). Every spanning tree has exactly n - 1 edges, so adding 1 to every weight adds the same n - 1 to every tree total and the ranking is untouched. Shortest paths do not survive the same shift, because two paths between the same pair can use different numbers of edges. For (ii), adding e to an MST that omits it creates a cycle. Replace a heavier cycle edge with e for a contradiction.
GATE 2009: trace the edge sequence
The seven-vertex graph has 12 edges: a-b 5, a-c 3, b-c 4, b-d 6, b-e 2, c-d 5, c-f 6, d-e 6, d-f 6, e-f 3, e-g 5, f-g 4. Sorted groups are 2: (b,e); 3: (a,c), (e,f); 4: (b,c), (f,g); 5: (a,b), (c,d), (e,g); then four weight-6 edges.
Kruskal keeps (b,e) 2, both 3s, both 4s, and (c,d) 5. Total: 2 + 3 + 3 + 4 + 4 + 5 = 21.
Q9. Which sequence is impossible? (GATE 2009)
(a) (b,e)(e,f)(a,c)(b,c)(f,g)(c,d)
(b) (b,e)(e,f)(a,c)(f,g)(b,c)(c,d)
(c) (b,e)(a,c)(e,f)(b,c)(f,g)(c,d)
(d) (b,e)(e,f)(b,c)(a,c)(f,g)(c,d)
Answer: (d). Options (a), (b), and (c) have weights 2, 3, 3, 4, 4, 5. Option (d) has 2, 3, 4, 3, 4, 5: (a,c) remains usable when the heavier (b,c) is taken. The decrease gives it away.
GATE 2003: compute the MST weight
This graph has ten vertices and 18 edges: a-b 6, a-c 1, a-d 2, a-e 8, b-d 3, b-g 2, c-d 2, d-h 15, e-f 11, e-h 8, e-i 2, f-h 4, f-i 9, g-h 8, g-i 14, g-j 19, h-i 4, i-j 5.
Kruskal takes a-c 1; c-d 2 (or a-d 2); b-g 2; e-i 2; b-d 3; h-i 4; f-h 4; i-j 5; and a joining edge of weight 8, such as g-h. Skip the other a-c-d triangle edge and a-b 6. Running total: 1, 3, 5, 7, 10, 14, 18, 23, 31.
Q10. Weight of the MST (GATE 2003)
What is the weight of a minimum spanning tree of the following graph?
(a) 29
(b) 31
(c) 38
(d) 41
Answer: (b). The accepted weights are 1, 2, 2, 2, 3, 4, 4, 5, and 8, totalling 31. Nine edges is the required n - 1 count for ten vertices.
Two state-exam numericals
A matrix is still an edge list. A maximisation twist still follows Kruskal's forced choices.
Q11. Road-network cost matrix (UPPSC Polytechnic Lecturer 2022)
There are 5 cities in a network. The cost of building a road directly between i & j is the entry C(i, j) in the matrix C below. An infinite entry indicates that there is a mountain in the way and so a road cannot be built. The least cost of making all the cities reachable from each other is:
C(i,j) | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
1 | 0 | 3 | 5 | 11 | 9 |
2 | 3 | 0 | 3 | 9 | 8 |
3 | 5 | 3 | 0 | ∞ | 10 |
4 | 11 | 9 | ∞ | 0 | 7 |
5 | 9 | 8 | 10 | 7 | 0 |
(a) 18
(b) 21
(c) 23
(d) None of the above
Answer: (b). Take (1-2) 3 and (2-3) 3; skip (1-3) 5, which closes a cycle. Take (4-5) 7 and (2-5) 8. Four edges connect five cities, totalling 3 + 3 + 7 + 8 = 21. Infinity simply removes edge (3-4).
Q12. Maximum possible MST weight (HPSC 2021)
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights 1, 2, 3, 4, 5 and 6. The maximum possible weight that a minimum weight spanning tree of G can have is:
(a) 5
(b) 8
(c) 7
(d) 20
Answer: (c). Kruskal must accept 1 and 2 because two edges cannot form a cycle. If 3 is usable, the total is 6. For the maximum, place 1, 2, and 3 on a triangle, so 3 is skipped. Weight 4 must then reach the fourth vertex and is accepted. The worst total is 1 + 2 + 4 = 7. Option (d) is unreachable: even the three heaviest edges, 4 + 5 + 6, come to only 15.
The short version and your next step
MST means all vertices, n - 1 acyclic edges, and minimum total weight.
Kruskal sorts edges, uses DSU to join different components, and stops at n - 1 edges.
Sorting dominates: O(m log m), often shown as O(n log n) in options.
Distinct weights guarantee uniqueness; adding 1 to every edge preserves the MST.
In sequence questions, reject a heavier edge taken before a lighter usable one.
In numericals, sum accepted weights and verify the edge count.
The three GATE questions above, from 2003, 2009 and 2017, sit in the minimum spanning tree section of GATE Guidance by Sanchit Sir. Work the two graph numericals again on paper before you move to Prim, because the sorted-edge habit is what carries across. Choose more practice from GATE CS preparation courses and test series.
