Question

Given below are two statements :
one is labelled as
Assertion (A) and the other is labelled as
Reason (R).
Assertion (A) :
Prim’s and Kruskal’s algorithms always produce the same minimum total weight spanning tree for a given connected, weighted graph.
Reason (R) :
Both algorithms use same greedy properties of choosing the minimum weight edge at each step.
In the light of the above statements, choose the most appropriate answer from the options given below :

• A. Both (A) and (R) are correct and (R) is the correct explanation of (A)
• B. Both (A) and (R) are correct but (R) is not the correct explanation of (A)
• C. (A) is correct but (R) is not correct
• D. (A) is not correct but (R) is correct

Hint:

Remember: Unique edge weights $\implies$ Unique MST. Duplicate edge weights $\implies$ Multiple possible MSTs!

Answer 1

The Correct Option is D

To evaluate these statements, we must understand the uniqueness of Minimum Spanning Trees (MSTs) and how greedy strategies are applied. 1. Analyzing Assertion (A): While both Prim's and Kruskal's algorithms are guaranteed to find a spanning tree with the minimum total weight, they do not necessarily produce the same set of edges. If a graph has multiple edges with the same weight, there can be several different MSTs. Depending on the starting vertex or the order in which equal-weight edges are processed, different trees may be generated. Therefore, Assertion (A) is incorrect. 2. Analyzing Reason (R): Both Prim's and Kruskal's algorithms are built on the greedy paradigm. They follow the "MST Property": at each step, they make a locally optimal choice (selecting the minimum weight edge that doesn't violate tree constraints) to reach a global optimum. Since they both rely on this fundamental greedy logic, Reason (R) is correct. 3. Final Logic: An MST is only unique if all edge weights are distinct. Since the assertion claims they always produce the same tree (even with duplicate weights) and the reason correctly identifies their shared greedy nature, Option (4) is the correct choice.