--- title: "MST definition; Kruskal's MST on 6-vertex graph" subject: "Data Structure and Algorithm" chapter: 10 key: "semester_4/data_structure_and_algorithm:mst-definition-kruskal-graph-i" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/mst-definition-kruskal-graph-i site: BCT Engineering --- # MST definition; Kruskal's MST on 6-vertex graph Data Structure and Algorithm · Chapter 10: Graphs - Asked in: 2070 Bhadra, 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/mst-definition-kruskal-graph-i - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10 ## Question What do you mean by minimum spanning tree? Find out the minimum spanning tree for given graph using Kruskal's algorithm. [Figure: undirected weighted graph on vertices A, B, C, D, E, F with edges A-B 2, A-C 6, A-F 7, B-D 11, C-F 3, C-E 5, D-F 9, E-F 1] ## Short answer A minimum spanning tree is a spanning tree with the smallest total edge weight. Kruskal's algorithm on this graph yields edges E-F(1), A-B(2), C-F(3), A-C(6), D-F(9), with minimum cost = 21. ## Answer #### Minimum spanning tree A **spanning tree** of a connected undirected graph G with V vertices is a subgraph that contains all V vertices, is connected and has no cycle (exactly V−1 edges). For a weighted graph, the spanning tree whose sum of edge weights is the smallest is the **minimum spanning tree (MST)**. It is used in network design (least cable, pipeline or road cost). #### Kruskal's algorithm on the given graph 6 vertices, so 5 edges are needed. Edges sorted: E-F 1, A-B 2, C-F 3, C-E 5, A-C 6, A-F 7, D-F 9, B-D 11. | Step | Edge | Weight | Decision | Total | |---|---|---|---|---| | 1 | E-F | 1 | accept | 1 | | 2 | A-B | 2 | accept | 3 | | 3 | C-F | 3 | accept | 6 | | 4 | C-E | 5 | reject (cycle C-E-F) | 6 | | 5 | A-C | 6 | accept | 12 | | 6 | A-F | 7 | reject (cycle) | 12 | | 7 | D-F | 9 | accept (5th edge) | 21 | **MST edges:** E-F, A-B, C-F, A-C, D-F. **Minimum cost = 21.** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. A spanning tree of a connected graph with V vertices must have which property? A. All V vertices, connected, no cycle, V-1 edges B. All V vertices, V edges, exactly one cycle C. All V vertices with every pair directly joined D. Only the vertices on the shortest path, V-1 edges Answer: A. A spanning tree covers every vertex, is connected and acyclic, so it has exactly V-1 edges. (Key point: Spanning tree definition) 2. Which spanning tree is the minimum spanning tree? A. The one with the shortest path between two chosen vertices B. The one that starts with the smallest-weight edge only C. The one with the smallest sum of edge weights D. The one with the fewest edges Answer: C. All spanning trees have V-1 edges; the MST is the one whose total weight is least. (Key point: MST meaning) 3. How does Kruskal's algorithm choose edges? A. Grow one tree from a start vertex, always taking the nearest vertex B. Add the heaviest edges first and remove cycles later C. Take edges in the order they are given in the graph D. Sort edges by weight and add each one unless it forms a cycle Answer: D. Kruskal sorts edges in increasing weight and accepts an edge only if it does not create a cycle. (Key point: Kruskal method) 4. Why is edge C-E (5) rejected in the given graph? A. Vertex E has already been used twice B. It is heavier than A-C C. C and E are already connected through F (cycle C-E-F) D. It would give more than 5 edges Answer: C. E-F and C-F are already accepted, so adding C-E forms the cycle C-E-F. (Key point: Rejecting C-E) 5. What is the MST of the graph and its cost? A. E-F, A-B, C-F, C-E, D-F with cost 20 B. E-F, A-B, C-F, A-C, D-F with cost 21 C. E-F, A-B, C-F, A-C, B-D with cost 23 D. E-F, A-B, C-F, A-C, A-F with cost 19 Answer: B. The accepted edges are 1+2+3+6+9 = 21 and they give 5 edges for 6 vertices. (Key point: Final MST cost) ## Related in Data Structure and Algorithm - [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 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× - [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×