---
title: "Spanning tree properties; Round Robin MST"
subject: "Data Structure and Algorithm"
chapter: 10
key: "semester_4/data_structure_and_algorithm:spanning-tree-properties-round-robin"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/spanning-tree-properties-round-robin
site: BCT Engineering
---

# Spanning tree properties; Round Robin MST

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2071 Magh, 2+8 marks
- 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/spanning-tree-properties-round-robin
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Write two properties of spanning tree. Find MST of graph-1 using Round Robin Algorithm.
[Figure: graph-1, undirected weighted graph on vertices a, b, c, d, e with edges a-b 9, a-d 2, b-d 6, a-c 5, c-d 4, d-e 4, b-e 5, c-e 5]

## Short answer

A spanning tree has V-1 edges and is connected and acyclic. Using Round Robin, the MST edges are a-d (2), c-d (4), d-e (4), b-e (5) with total cost 15.

## Answer

#### Two properties of a spanning tree
1. A spanning tree of a connected graph with V vertices contains **exactly V−1 edges** and all V vertices.
2. It is **connected and acyclic**: there is exactly one path between any two vertices, and adding any non-tree edge creates exactly one cycle.

(Also: removing any edge disconnects it; a graph can have many spanning trees.)

#### MST of graph-1 by Round Robin
**Round Robin algorithm** (Yao / Cheriton-Tarjan) builds an MST by merging trees. Start with every vertex as a separate tree placed in a queue. Repeat: remove the tree T at the front, find the minimum-weight edge leaving T, merge T with the tree at the other end of that edge (remove that tree from the queue), and add the merged tree to the rear. Stop when one tree remains.

Edges: a-b 9, a-d 2, b-d 6, a-c 5, c-d 4, d-e 4, b-e 5, c-e 5. Initial queue: [a] [b] [c] [d] [e].

| Step | Tree taken | Cheapest edge leaving it | Merge | Queue after |
|---|---|---|---|---|
| 1 | {a} | a-d (2) | with {d} | [b] [c] [e] [a,d] |
| 2 | {b} | b-e (5) | with {e} | [c] [a,d] [b,e] |
| 3 | {c} | c-d (4) | with {a,d} | [b,e] [a,c,d] |
| 4 | {b,e} | d-e (4) | with {a,c,d} | [a,b,c,d,e] |

One tree remains.

**MST edges:** a-d (2), c-d (4), b-e (5), d-e (4). **Minimum cost = 2 + 4 + 5 + 4 = 15.**

```text
a --2-- d --4-- c
        |
        4
        |
        e --5-- b
```
The result equals the Kruskal result (15).

## 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 contains how many edges?
   A. 2V-1
   B. V+1
   C. V
   D. V-1
   Answer: D. A tree on V vertices has exactly V-1 edges. (Key point: Edge count property)

2. What happens when a non-tree edge is added to a spanning tree?
   A. It becomes disconnected
   B. Nothing, it stays a tree
   C. It creates exactly one cycle
   D. It creates a cycle at every vertex
   Answer: C. A tree has exactly one path between two vertices, so an extra edge closes exactly one cycle. (Key point: Acyclic property)

3. In Round Robin, what is done with the tree taken from the front of the queue?
   A. It is deleted and its edges discarded
   B. Its heaviest outgoing edge is added
   C. It is joined by its cheapest outgoing edge to another tree, and the merged tree goes to the rear
   D. It is merged with the tree at the rear of the queue regardless of weight
   Answer: C. The front tree takes its minimum-weight edge leaving it, merges with the tree at the other end, and the result is queued at the rear. (Key point: Round Robin procedure)

4. How does Round Robin begin?
   A. With the lightest edge only
   B. With a sorted list of all edges
   C. With one tree containing all vertices
   D. With every vertex as its own tree in the queue
   Answer: D. Each vertex starts as a single-vertex tree in the queue. (Key point: Starting state)

5. What is the MST cost of graph-1 found by Round Robin?
   A. 20
   B. 17
   C. 13
   D. 15
   Answer: D. Edges a-d 2, c-d 4, d-e 4, b-e 5 give 15. (Key point: Result for graph-1)

## Related in Data Structure and Algorithm

- [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 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×
- [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×
- [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

## Related in other subjects

- [Round robin scheduling (9, 6, 3 ms, q=2)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-rr-9-6-3-q2) — Embedded System, chapter 6, asked 4×
- [Round robin scheduling (9, 6, 3 ms, q=3)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-rr-9-6-3-q3) — Embedded System, chapter 6, asked 4×
- [Round robin scheduling (6, 4, 2 ms, q=2)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-rr-6-4-2-q2) — Embedded System, chapter 6, asked 4×
- [Round robin scheduling (53, 17, 68, 24 ms)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-rr-53-17-68-24-q4) — Embedded System, chapter 6, asked 4×