Kruskal's Algorithm and MST Explained: A Step-by-Step Worked Example
Learn what an MST is, how DSU makes Kruskal's cycle decisions, and how a seven-vertex graph reaches six selected edges with total weight 14.
KnowledgeGate Team
Exam prep & CS education

An MST is not merely a low-weight collection of edges. Kruskal's algorithm is also not simply "keep taking the smallest edge", because every choice must preserve acyclicity. The seven-vertex graph reaches an MST of weight 14 through sorted edges and cycle checks, illustrating selection-order, total-weight, and trap-based exam questions.
Minimum spanning trees: the object Kruskal is trying to build
A weighted, undirected graph uses two-way edges with weights. A spanning subgraph includes every vertex; connected means a path exists between each pair. A tree is connected and acyclic, while a cycle is a closed path. Total edge weight is the edge-weight sum.
For a connected graph with V vertices, every spanning tree has exactly V - 1 edges. A minimum spanning tree, or MST, has the smallest total weight. More than one tree may share that minimum.
For {P,Q,R} with PQ=2, QR=3, and PR=8, {PQ,QR} weighs 2+3=5. The alternatives weigh 2+8=10 and 3+8=11. An MST minimises the sum, not the largest edge alone.
The standard MST problem assumes a connected, undirected weighted graph. Review the graph traversal and shortest-path foundations, but distinguish the goals: an MST minimises total tree weight; a shortest-path tree preserves routes from one source.
Kruskal's algorithm: sorted edges plus disjoint sets
Kruskal grows a forest and has no starting vertex:
Make one component per vertex.
Sort edges by non-decreasing weight.
Scan them in order.
Accept only between different components, then merge them.
Stop at
V - 1accepted edges.
A disjoint-set union structure, or DSU, makes the test efficient. find(x) identifies x's component representative. If find(u) == find(v), (u,v) would close a cycle; otherwise, union(u,v) merges the components. Union by rank or size and path compression are optimisations, not different greedy decisions.
The cut idea says the lightest available edge joining two current components is safe. This is the relevant greedy choice and exchange reasoning. "Smallest edges are always safe" is incomplete without the different-component condition.
Worked example: compute the MST edge by edge
Use vertices {A,B,C,D,E,F,G} and edges AB=4, AC=3, BC=1, BD=2, CD=4, CE=2, DE=3, DF=6, EF=5, EG=4, FG=2. Since V=7, the target is six accepted edges. One deterministic sorted order is:
BC(1), BD(2), CE(2), FG(2), AC(3), DE(3), AB(4), CD(4), EG(4), EF(5), DF(6)
Equal-weight edges may use another legal order. This order gives:
Edge | Weight | Find endpoints same? | Decision | Components after decision | Running MST weight |
|---|---|---|---|---|---|
BC | 1 | No | Accept |
| 1 |
BD | 2 | No | Accept |
| 3 |
CE | 2 | No | Accept |
| 5 |
FG | 2 | No | Accept |
| 7 |
AC | 3 | No | Accept |
| 10 |
DE | 3 | Yes | Reject, cycle |
| 10 |
AB | 4 | Yes | Reject, cycle |
| 10 |
CD | 4 | Yes | Reject, cycle |
| 10 |
EG | 4 | No | Accept and stop |
| 14 |
The edge set is {BC,BD,CE,FG,AC,EG}, with weight 1+2+2+2+3+4=14. After six acceptances, EF(5) and DF(6) remain unused.


Why the result is correct, not just plausible
Before EG(4), the components are {A,B,C,D,E} and {F,G}. Their crossing edges are EG=4, EF=5, and DF=6, so EG is safe. Earlier acceptances pass the same component-crossing test.
Once {A,B,C,D,E} is connected, DE=3, AB=4, and CD=4 each closes a cycle. Rejection depends on current components, not apparent expense. At completion, all seven vertices share one component and 7-1=6 edges are accepted. These checks do not replace the algorithm on arbitrary input.
Ties, uniqueness, disconnected graphs, and Kruskal versus Prim
Equal weights are valid. Here BD, CE, and FG weigh 2, while AB, CD, and EG weigh 4. A written solution benefits from a fixed tie rule, but equal weights do not automatically mean multiple MSTs.
For example, in cycle P-Q-R-S-P, let PQ=QR=RS=SP=1 and PR=QS=2. Any three perimeter edges form an MST of weight 3, giving four MSTs. Distinct edge weights, however, guarantee a unique MST.
For a disconnected example, vertices {A,B,C,D,E} with AB=1, BC=2, AC=4, and DE=3 produce the minimum spanning forest {AB,BC,DE} of weight 1+2+3=6. No single spanning tree exists. Kruskal is edge-centric: it sorts all edges and joins DSU components. Prim's Algorithm and Minimum Spanning Tree owns the complementary frontier trace: it grows from one chosen vertex and updates the cheapest crossing edge. The minimum weight agrees, but the state you track is different.
Complexity and implementation checklist
for each v in vertices: makeSet(v)
sort(edges) by numeric weight
mstWeight = 0; selectedEdges = 0
for (u, v, w) in edges:
if find(u) != find(v):
union(u, v)
mstWeight += w; selectedEdges += 1
if selectedEdges == V - 1: break
if selectedEdges != V - 1: report minimum spanning forest
else: report MST and mstWeightSorting costs O(E log E). Path compression plus union by rank or size makes DSU operations O(E alpha(V)) amortised. The usual total is O(E log E), with O(V) auxiliary DSU space apart from edges and result.
Traps include sorting weights as strings, applying Kruskal to a directed graph, forgetting isolated vertices, adding before checking representatives, unioning labels instead of roots, and reporting an MST with fewer than V - 1 accepted edges.
How exams test Kruskal and where marks are lost
Four checks follow from the graph. Through DE(3), five edges are accepted, one is rejected, weight is 10, and two components remain. AB(4) and CD(4) are then rejected. EG(4) completes six edges at weight 14.
Recurring past-paper-style forms, not a guaranteed paper pattern, ask for edge order, cost, components after k scans, first rejection, DSU state, uniqueness, or a changed weight. The traps have short fixes:
"Take the first
V - 1sorted edges": check components before every acceptance."Kruskal starts from the lightest vertex": it has no start vertex.
"Only a triangle can be a cycle": DSU detects cycles of any length.
"Negative edges break MST": they are valid and appear early in sorted order.
"Same weight means the same tree": a tie order can change the tree while preserving minimum weight.
Use the GATE CS courses and practice routes to place MST inside the wider syllabus, then use timed mock and subject-wise test practice to check whether the process still holds under time pressure.
Kruskal checkpoint: rebuild the trace after one weight changes
A reliable Kruskal trace has three checkpoints: the edge order is non-decreasing, every accepted edge joins different DSU representatives, and a connected graph stops after V - 1 acceptances. The accepted weights must sum to the reported total.
The result is {BC,BD,CE,FG,AC,EG}, total 14. Redraw the graph, hide the decisions, and rebuild the sorted list and DSU table. Then change EG from 4 to 7. After the same first five acceptances, EF=5 is the cheapest connection between {ABCDE} and {FG}. The new MST is {BC,BD,CE,FG,AC,EF}, total 1+2+2+2+3+5=15; DF=6 and EG=7 stay unused.
After rebuilding the trace and the changed-weight variant, use GATE Guidance by Sanchit Sir for a structured route through the wider Algorithms syllabus.
Keep learning
Kruskal's Algorithm Interview Questions: MST Traces, DSU and Model Answers
Trace Kruskal's algorithm on a six-vertex graph, then rehearse model answers on DSU, correctness, complexity, ties, negative weights and disconnected inputs.
MST and Kruskal's Algorithm MCQs: 12 Solved Questions with Explanations
Test your MST fundamentals across 12 solved MCQs. Each answer explains the shortcut, trap, or Kruskal trace you need for exam questions.
Prim's Algorithm and Minimum Spanning Tree: Worked Example, Complexity and Exam Traps
Learn what makes Prim's greedy choice safe, trace every key update on a six-vertex graph, and avoid the mistakes that derail MST questions.
Prim's Algorithm MCQs: 12 Solved MST Questions with Explanations
Solve 12 Prim's algorithm and minimum spanning tree questions, then check each answer against a concise explanation, one full trace and two diagrams.





