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

# Kruskal's MST on 7-vertex graph

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2074 Bhadra, 6 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-74
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Create minimum spanning tree for the following graph using Kruskal's algorithm.
[Figure: undirected weighted graph on vertices A to G with edges A-B 5, A-C 2, A-D 6, B-D 3, B-F 2, B-G 3, C-D 4, C-E 1, D-F 2, D-G 4, E-F 6, F-G 1]

## Short answer

Using Kruskal, sort edges: C-E1, F-G1, A-C2, B-F2, D-F2, C-D4 accepted; B-D3, B-G3 rejected. MST edges: C-E, F-G, A-C, B-F, D-F, C-D. Minimum cost = 12.

## Answer

Edges of the graph (A to G, 7 vertices, so the MST needs 6 edges), sorted by weight:
C-E 1, F-G 1, A-C 2, B-F 2, D-F 2, B-D 3, B-G 3, C-D 4, D-G 4, A-B 5, A-D 6, E-F 6.

| Step | Edge | Weight | Decision | Components after |
|---|---|---|---|---|
| 1 | C-E | 1 | accept | {C,E} |
| 2 | F-G | 1 | accept | {F,G} |
| 3 | A-C | 2 | accept | {A,C,E} |
| 4 | B-F | 2 | accept | {B,F,G} |
| 5 | D-F | 2 | accept | {B,D,F,G} |
| 6 | B-D | 3 | reject (B, D already connected) | |
| 7 | B-G | 3 | reject (cycle B-F-G) | |
| 8 | C-D | 4 | accept | {A,B,C,D,E,F,G} |

Six edges selected, stop.

```text
        E
        | 1
A --2-- C --4-- D --2-- F --2-- B
                        |
                        1
                        G
```
Edges of the MST: C-E, F-G, A-C, B-F, D-F, C-D.

**Minimum cost = 1 + 1 + 2 + 2 + 2 + 4 = 12.**

## Check yourself

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

1. How many edges does the MST of 7 vertices have?
   A. 7
   B. 5
   C. 8
   D. 6
   Answer: D. V - 1. (Key point: Edges needed)

2. Why is B-D (3) rejected?
   A. B and D are already connected
   B. Weight too high
   C. D is isolated
   D. It's duplicate
   Answer: A. B-F and D-F joined them. (Key point: Rejected B-D)

3. Which weight-4 edge is accepted?
   A. D-G
   B. C-D
   C. B-G
   D. A-B
   Answer: B. It joins {A,C,E} with {B,D,F,G}. (Key point: Edge accepted at weight 4)

4. Minimum cost?
   A. 14
   B. 10
   C. 12
   D. 11
   Answer: C. 1+1+2+2+2+4 = 12. (Key point: Cost)

## Close variants set in other exams

- [Kruskal's MST on 9-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-mst-graph-f) — 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×