---
title: "Kruskal's MST on 9-vertex graph"
subject: "Data Structure and Algorithm"
chapter: 10
key: "semester_4/data_structure_and_algorithm:kruskal-mst-graph-f"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/kruskal-mst-graph-f
site: BCT Engineering
---

# Kruskal's MST on 9-vertex graph

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2072 Magh, 5 marks
- Video: [6.6 Kruskals Algorithm for Minimum Spanning Tree- Greedy method | Data structures](https://www.youtube.com/watch?v=EjVHtpWkIho) — Jenny's Lectures CS IT
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/kruskal-mst-graph-f
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Find the minimum spanning tree of the following graph using Kruskal's algorithm.
[Figure: undirected weighted graph on vertices a, b, c, d, e, f, g, h, i with edges a-b 4, b-c 8, c-d 7, d-e 9, e-f 10, f-g 2, g-h 1, h-a 8, b-h 11, h-i 7, i-g 6]

## Short answer

Kruskal sorts edges: g-h1, f-g2, a-b4, i-g6, c-d7, b-c8, h-a8, d-e9 accepted; h-i7 rejected. MST edges: g-h, f-g, a-b, i-g, c-d, b-c, h-a, d-e. Minimum cost = 45.

## Answer

Graph with 9 vertices a to i, so the MST has 8 edges. Sort the edges:
g-h 1, f-g 2, a-b 4, i-g 6, c-d 7, h-i 7, b-c 8, h-a 8, d-e 9, e-f 10, b-h 11.

| Step | Edge | Weight | Decision | Total |
|---|---|---|---|---|
| 1 | g-h | 1 | accept | 1 |
| 2 | f-g | 2 | accept | 3 |
| 3 | a-b | 4 | accept | 7 |
| 4 | i-g | 6 | accept | 13 |
| 5 | c-d | 7 | accept | 20 |
| 6 | h-i | 7 | reject (h, i already connected through g) | 20 |
| 7 | b-c | 8 | accept | 28 |
| 8 | h-a | 8 | accept (joins {a,b,c,d} with {f,g,h,i}) | 36 |
| 9 | d-e | 9 | accept (adds e, 8th edge) | 45 |

**MST edges:** g-h, f-g, a-b, i-g, c-d, b-c, h-a, d-e. **Minimum cost = 45.**

```text
e -9- d -7- c -8- b -4- a -8- h -1- g -2- f
                                    |
                                    6
                                    |
                                    i
```

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How many edges in the MST of 9 vertices?
   A. 9
   B. 7
   C. 8
   D. 10
   Answer: C. V - 1. (Key point: Edges)

2. Why is h-i (7) rejected?
   A. Too heavy
   B. i is isolated
   C. Duplicate
   D. h and i are connected through g
   Answer: D. g-h and i-g exist. (Key point: Rejected h-i)

3. Minimum cost?
   A. 45
   B. 37
   C. 52
   D. 48
   Answer: A. 1+2+4+6+7+8+8+9 = 45. (Key point: Cost)

## Close variants set in other exams

- [Kruskal's MST on 7-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-mst-graph-74) — Data Structure and Algorithm, chapter 10, asked 3×
- [Kruskal's MST on graph A to G](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-mst-graph-d) — Data Structure and Algorithm, chapter 10, asked 3×

## Related in Data Structure and Algorithm

- [MST definition; Kruskal's MST on 6-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amst-definition-kruskal-graph-i) — Data Structure and Algorithm, chapter 10
- [Spanning tree properties; Round Robin MST](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aspanning-tree-properties-round-robin) — Data Structure and Algorithm, chapter 10
- [Round Robin MST on 7-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Around-robin-mst-graph-l) — Data Structure and Algorithm, chapter 10
- [Kruskal's algorithm with example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-algorithm-example) — Data Structure and Algorithm, chapter 10, asked 3×
- [Write Kruskal's algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-algorithm-write) — Data Structure and Algorithm, chapter 10, asked 3×