Prim's Algorithm MCQs: 12 Solved MST Questions with Explanations

Prim's algorithm questions expose a common mistake: choosing beside the latest vertex instead of across the whole tree frontier. A correct attempt compares every edge from the current tree to an unvisited vertex. The cut property makes the cheapest frontier edge safe, and a min-priority queue maintains those choices efficiently. Attempt each question before reading its explanation. The Algorithms learn module provides more graph practice.

Related reading: Minimum spanning trees and Graph MCQs.

How Prim's grows a tree, and the cut property behind it

Prim's keeps one connected tree, unlike Kruskal's forest. It adds the cheapest edge with one endpoint inside. The cut property makes that crossing edge safe for some MST.

Q1. Choosing the next node

In Prim's algorithm, after the start vertex has been selected, which rule chooses the next edge?

(a) The minimum-weight edge from the current tree to an unvisited vertex; (b) The maximum-weight edge from the current tree to an unvisited vertex; (c) Any edge incident on the latest vertex; (d) The median-weight edge incident on the latest vertex

Answer: (a). Compare every edge with one endpoint in the current tree and the other outside it. Looking only beside the most recently added vertex can miss a cheaper frontier edge.

Q2. Bihar STET 2025 solved question

In minimum spanning trees, the cut property is used to justify Prim's algorithm. What does the cut property state?

(a) A maximum-weight edge in the graph must be part of every MST. (b) A minimum-weight edge in the graph is the only edge Prim's algorithm can choose. (c) A minimum-weight edge crossing the current cut is safe to add to an MST. (d) A maximum-weight edge crossing a cut is safe to add to an MST.

Answer: (c). A cut splits vertices into two non-empty sets; crossing edges join them. Prim separates tree from rest. Option (b) confuses this cut minimum with the graph's global minimum.

One full Prim's trace with actual numbers

Take vertices A, B, C, D, E and edges A-B = 4, A-C = 1, C-B = 2, B-D = 3, C-D = 5, D-E = 6, C-E = 7. Start at A.

1. From {A}, compare A-B (4) and A-C (1). Choose A-C (1).

2. From {A, C}, compare A-B (4), C-B (2), C-D (5), C-E (7). Choose C-B (2).

3. From {A, B, C}, compare B-D (3), C-D (5), C-E (7). Choose B-D (3); A-B is now internal.

4. From {A, B, C, D}, compare D-E (6) and C-E (7). Choose D-E (6).

The MST {A-C, C-B, B-D, D-E} costs 1 + 2 + 3 + 6 = 12. A-B lost twice to cheaper crossing edges, demonstrating the cut property.

Prim vs Kruskal: what each one needs

Kruskal sorts all edges and uses union-find to grow a forest. The earlier MST and Kruskal's Algorithm MCQs owns that edge-sorted and DSU treatment. Prim stays with one connected tree and a min-priority queue, updating each outside vertex's cheapest connection to the tree.

Q3. Working without sorted edges

For constructing an MST, which algorithm can work efficiently without sorting all graph edges by weight first?

(a) Kruskal's Algorithm; (b) Dijkstra's Algorithm; (c) Floyd-Warshall Algorithm; (d) Prim's Algorithm

Answer: (d). Prim maintains the cheapest tree-to-outside choices in a priority queue. Kruskal sorts edges globally; Dijkstra and Floyd-Warshall solve shortest-path problems rather than MSTs.

Q4. Coal India 2020 solved question

Which of the following statement is false about Prim's algorithm?

(a) Initially the root's key is initialized to 0 and all other nodes to infinity; (b) It may use binomial max heap to represent the priority queue; (c) The complexity is O(E log V) using binary heap; (d) The time complexity is O(E + V log V) using Fibonacci Heap

Answer: (b). Prim needs a min-heap. A max-heap returns the costliest frontier edge, opposing its greedy rule. The other statements are correct.

What Prim's costs, and what re-checking an MST costs

The bounds are O(V^2) with a matrix, O(E log V) with adjacency lists and a binary heap, and O(E + V log V) with a Fibonacci heap. For E near V^2, the matrix is optimal.

Q5. Binary-heap complexity

What is the time complexity of Prim's Minimum Spanning Tree algorithm, when implemented using Binary Heap?

(a) O(V+E); (b) O(V log V); (c) O(E log E); (d) O(E log V)

Answer: (d). V extract-mins and up to E updates cost O((V + E) log V) = O(E log V), since connected graphs have E >= V - 1. Although log E <= 2 log V, Prim's expected form is O(E log V).

Q6. GATE 2020 solved question

Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u, v) in V x V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

(a) Theta(|E| + |V|); (b) Theta(|E| |V|); (c) Theta(|E| log |V|); (d) Theta(|V|)

Answer: (d). The new edge plus T's unique u-to-v path forms one cycle. T remains minimum unless the new edge is lighter than the path maximum. DFS or BFS on T's |V| - 1 edges takes Theta(|V|), not E. See Graph Algorithms: BFS, DFS and Shortest Paths.

Minimum-weight edges and MST uniqueness

Distinct weights imply a unique MST. A minimum-weight edge belongs to some MST, not every MST. An all-weight-1 triangle has three MSTs, each omitting one edge.

Q7. GATE 2007 solved question

Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w. Which of the following is FALSE?

(a) There is a minimum spanning tree containing e. (b) If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight. (c) Every minimum spanning tree has an edge of weight w. (d) e is present in every minimum spanning tree.

Answer: (d). The equal-weight triangle's {X-Z, Y-Z} omits e = X-Y. Adding e and deleting a cycle edge proves (a). A cycle edge above w could be replaced to improve T; hence all have weight w, proving (b) and (c).

Q8. GATE 2021 solved question

Let G be a connected undirected weighted graph. Consider the following two statements.

S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.

S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree.

(a) Both S1 and S2 are true; (b) S1 is true and S2 is false; (c) S1 is false and S2 is true; (d) Both S1 and S2 are false

Answer: (c). The equal-weight triangle disproves S1: every edge is minimum, but none is universal. Distinct weights remove greedy ties, so exchange proves S2.

Q9. GATE 2019 solved question

Let G be any connected, weighted, undirected graph.

I. G has a unique minimum spanning tree, if no two edges of G have the same weight.

II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.

(a) I only; (b) II only; (c) Both I and II; (d) Neither I nor II

Answer: (c). Statement I follows from the distinct-weight uniqueness theorem. In II, every cut's unique cheapest edge is forced, preventing two MSTs. Both are sufficient conditions; II is not necessary.

Transforming weights and structured graphs

MSTs depend on edge-weight order. Strictly increasing transformations preserve order, but not total formulas.

Q10. GATE 2012 solved question

Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?

(a) T' = T with total weight t' = t^2; (b) T' = T with total weight t' < t^2; (c) T' is not equal to T but total weight t' = t^2; (d) None of the above

Answer: (d). Squaring preserves comparisons and the MST set, not total formulas. For edges 2 and 3, t = 5 and t' = 4 + 9 = 13 < 25 = t^2, disproving (a). For one edge weighing 2, t' = 4 = t^2, so (b) is not always strict; (c) is not guaranteed.

Q11. GATE 2006 solved question

Consider a weighted complete graph G on the vertex set {v1, v2, ..., vn} such that the weight of the edge (vi, vj) is 2|i-j|. The weight of a minimum spanning tree of G is:

(a) n - 1; (b) 2n - 2; (c) nC2; (d) 2

Answer: (b). Consecutive pairs have minimum weight 2. The path v1 - v2 - ... - vn uses n - 1 of them, costing 2(n - 1) = 2n - 2. At n = 3, it costs 2 + 2 = 4.

One NAT workout: the worst best tree

Arrange weights 1 to 6 on a complete four-vertex graph to maximise its MST. The Kruskal collection above uses this same graph to test sorted-edge acceptance. A Prim trace starts at the fourth vertex and follows the changing frontier.

Q12. GATE 2016 solved question

Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is _________.

Answer: 7. Label the triangle A-B-C with AB = 1, AC = 2 and BC = 3; connect D by DA = 4, DB = 5 and DC = 6. Starting at D, Prim chooses D-A (4), then A-B (1), then A-C (2), for 7. No arrangement can do better: the two lightest edges cannot form a cycle, so every MST accepts 1 and 2. Placing weight 3 on their triangle is the only way to reject it, after which weight 4 is the cheapest edge that can reach the fourth vertex.

The short version and your next step

• Prim's chooses the cheapest tree-to-outside edge.

• Use a min-heap: O(V^2), O(E log V), or O(E + V log V).

• Distinct weights guarantee uniqueness; a minimum-weight edge need not be in every MST.

• Order-preserving transforms preserve MSTs, but not total-weight formulas.

• Re-check one added edge in Theta(V) on the tree path.

Retry the linked PYQs without notes, then compare every choice against the full tree frontier. Continue with GATE Guidance by Sanchit Sir for worked graph lessons, or use GATE CS Exam Preparation Courses & Test Series.