---
title: "Short note: Spanning tree and applications"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:spanning-tree-and-applications"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/spanning-tree-and-applications
site: BCT Engineering
---

# Short note: Spanning tree and applications

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2070 Magh, 3 marks
- Video: [Recognizing and Finding Spanning Trees in Graph Theory](https://www.youtube.com/watch?v=b233VKD6udo) — Ms. Hearn
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/spanning-tree-and-applications
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Write a short note on spanning tree and its applications.

## Short answer

A spanning tree of a connected graph is a subgraph containing all vertices and exactly n-1 edges with no cycles. Applications include designing minimum-cost networks, avoiding loops in Ethernet LANs via spanning-tree protocol, and clustering or image segmentation.

## Answer

A **spanning tree** of a connected graph G is a subgraph that contains all the vertices of G and is a tree (connected, with no cycles). Every spanning tree of a graph with n vertices has n − 1 edges. One can be found by removing edges from cycles until no cycles are left, or by a DFS/BFS traversal.

```text
  G:  a --- b          one spanning tree:  a --- b
      |  \  |                              |      
      d --- c                              d --- c      (edges ab, ad, dc)
```
G (a square with diagonal ac) has 4 vertices and 5 edges; each spanning tree keeps 3 of them.

In a weighted graph, the **minimum spanning tree** has the least total weight. It is found by Kruskal's algorithm (repeatedly add the cheapest edge that does not create a cycle) or Prim's algorithm (grow the tree from a vertex using the cheapest connecting edge).

**Applications:**
- Designing the cheapest network of cables, pipes or roads connecting all sites.
- Network protocols: the spanning-tree protocol avoids loops in switched LANs; broadcasting and multicast routing.
- Approximating the travelling salesman problem.
- Image segmentation and clustering.

## Check yourself

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

1. What is a spanning tree of a connected graph G?
   A. A subgraph that includes all vertices of G and is a tree
   B. Any subgraph that contains a cycle
   C. A subgraph containing only the leaves of G
   D. A complete subgraph of G
   Answer: A. It spans all vertices, is connected and has no cycles. (Key point: Definition)

2. A connected graph with 4 vertices and 5 edges: how many edges does each spanning tree keep?
   A. 5
   B. 4
   C. 2
   D. 3
   Answer: D. A tree on n vertices has n - 1 edges, so 3. (Key point: Edge count)

3. Which pair of algorithms finds a minimum spanning tree?
   A. DFS and BFS
   B. Kruskal's and Prim's
   C. Dijkstra's and Ford-Fulkerson
   D. Quick sort and merge sort
   Answer: B. Kruskal adds the cheapest edge that creates no cycle; Prim grows from a vertex by the cheapest connecting edge. (Key point: Minimum spanning tree)

4. Which is a listed application of spanning trees?
   A. Sorting numbers in ascending order
   B. Evaluating prefix expressions only
   C. Avoiding loops in switched LANs (spanning-tree protocol)
   D. Computing matrix determinants
   Answer: C. The spanning-tree protocol removes redundant links to avoid loops; also used in cheapest network design. (Key point: Application)

## Related in Discrete Structure

- [Short note: Spanning tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aspanning-tree-short-note) — Discrete Structure, chapter 4, asked 3×
- [Define tree; properties and applications](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Atree-definition-properties-applications) — Discrete Structure, chapter 4

## Related in other subjects

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