An MST numerical should end with two checks: the tree has V-1 edges, and an independent algorithm gives the same minimum cost. GATE questions then add a conceptual twist about a safe edge, an impossible edge, or whether equal weights create several minimum trees. One worked graph is enough to connect all of these ideas.
What a minimum spanning tree must satisfy
For a connected, undirected, weighted graph, a spanning tree includes every vertex, stays connected, and contains no cycle. A graph with V vertices therefore contributes exactly V-1 edges to any spanning tree. An MST is a spanning tree with minimum total edge weight.
Kruskal and Prim are greedy, but their choices are justified by two properties:
Cut property: for a cut that splits the vertices into two non-empty groups, a uniquely lightest crossing edge is in every MST.
Cycle property: in a cycle, a uniquely heaviest edge is in no MST.
The graph algorithms guide helps separate MST problems from shortest-path problems. An MST minimises the sum of tree edges, not the distance from one source.
The worked graph
Use vertices A, B, C, D, E and these undirected edges:
Edge | Weight |
|---|---|
A-B | 1 |
B-D | 2 |
B-C | 3 |
A-C | 4 |
C-D | 5 |
C-E | 6 |
D-E | 7 |
Five vertices mean the final tree must have four edges. All weights are distinct, so this example will also have a unique MST.
Kruskal's algorithm, edge by edge
Sort edges by increasing weight. Accept an edge if its endpoints are currently in different components, and reject it if it closes a cycle.
Accept
A-B (1). Components become{A,B},{C},{D},{E}.Accept
B-D (2). Components become{A,B,D},{C},{E}.Accept
B-C (3). Components become{A,B,C,D},{E}.Reject
A-C (4). It closes cycleA-B-C-A.Reject
C-D (5). It closes cycleB-C-D-B.Accept
C-E (6). The tree now has four edges, so stop.
Kruskal returns {A-B, B-D, B-C, C-E}. Its cost is
1 + 2 + 3 + 6 = 12.
Prim's algorithm on the same graph
Start at A. At each step, take the lightest edge with one endpoint inside the growing tree and one outside.
Step | Vertices already in tree | Crossing candidates | Choice |
|---|---|---|---|
1 | {A} | A-B (1), A-C (4) | A-B (1) |
2 | {A,B} | B-D (2), B-C (3), A-C (4) | B-D (2) |
3 | {A,B,D} | B-C (3), A-C (4), D-C (5), D-E (7) | B-C (3) |
4 | {A,B,C,D} | C-E (6), D-E (7) | C-E (6) |
Prim returns the same four edges. Its independently summed cost is also 1 + 2 + 3 + 6 = 12. Agreement does not replace the correctness proof, but it is an excellent arithmetic and edge-selection check.
Cut and cycle properties as GATE tests them
Before accepting A-B, consider the cut {A} and {B,C,D,E}. Its crossing edges are A-B (1) and A-C (4), so the uniquely lightest edge A-B is safe. This is a direct cut-property question.
When Kruskal reaches A-C (4), accepted edges already provide path A-B-C with weights 1 and 3. Adding A-C creates a cycle in which weight 4 is uniquely heaviest, so the cycle property rejects it. The same check rejects C-D (5) against path C-B-D, whose edge weights are 3 and 2.
If a new edge (u,v) is added to an existing MST, place it into the tree. It creates exactly one cycle. If the new edge is lighter than the heaviest edge on that cycle, replace that heaviest edge. If it is heavier, the current MST remains optimal. A tie can preserve the cost while creating another MST.
When is the MST unique?
If every edge weight is distinct, the MST is unique. Suppose two minimum trees differ. Take the lightest edge e present in one but not the other. Adding e to the second tree creates a cycle containing an edge f absent from the first. Distinct weights and the choice of e force w(e) < w(f). Replacing f by e makes the second tree lighter, contradicting its minimum status.
The converse is false. Equal weights do not automatically mean multiple MSTs. In a triangle with XY=1, YZ=1, and XZ=2, the only MST uses XY and YZ, with cost 1+1=2. The two alternatives each cost 3.
Equal weights can create several MSTs. In the four-cycle P-Q-R-S-P, let PQ=1, RS=1, QR=2, and SP=2. Every spanning tree removes one cycle edge. A minimum tree must retain both weight-1 edges and choose exactly one weight-2 edge. Therefore there are exactly two MSTs:
{PQ, RS, QR}, cost1+1+2=4{PQ, RS, SP}, cost1+1+2=4
For a larger graph, process equal-weight edges as a group. Contract components formed by lower weights, identify which tied edges can connect the contracted components without a cycle, and count the valid choices. Do not multiply local choices unless they are independent.
Complexity and implementation choices
Kruskal sorts edges and uses disjoint-set union, giving O(E log E). Prim with an adjacency list and binary heap gives O(E log V). A matrix-based Prim implementation takes O(V^2) and can suit dense graphs.
These complexities are often paired with representation questions. The data structures question set is useful for revising heaps and disjoint sets around the algorithm itself. About 1,100 published Algorithm questions in the KnowledgeGate bank provide further practice across this cluster.
How GATE frames MST questions
Expect an edge order, final weight, safe-edge statement, update after adding an edge, or a count of distinct MSTs. On any numerical, stop after V-1 accepted edges and add the weights a second time. Confirm current paper instructions on the official GATE portal of the organising IIT.
The short version
Kruskal grows a forest by sorted edges. Prim grows one tree by lightest crossing edges. Both are applications of the cut property, while cycle rejection uses the cycle property. Distinct weights guarantee one MST; repeated weights require actual counting.
Re-run the worked graph from another Prim start vertex and verify that the cost remains 12. Then use the GATE Test Series for timed algorithm practice, and the GATE category page to choose the next subject drill.
