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

# Short note: Spanning tree

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2073 Magh, 4 marks; 2072 Asoj, 3 marks; 2068 Bhadra, 3 marks (asked 3 times)
- Video: [Discrete Mathematics : Spanning Trees](https://www.youtube.com/watch?v=TzLswrllE7E) — Dragonfly Statistics
- 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-short-note
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Write a short note on spanning trees.

## Short answer

A spanning tree is a subgraph that includes all vertices, is connected, and has no cycles, with exactly n−1 edges. It can be found via DFS/BFS. A minimum spanning tree minimizes total edge weight; algorithms like Kruskal's and Prim's find it.

## Answer

A **spanning tree** of a connected graph G is a subgraph that is a tree and contains **all** the vertices of G. If G has n vertices, every spanning tree has exactly n − 1 edges; it is obtained by deleting edges to break all cycles while keeping the graph connected.

Facts:
- A graph has a spanning tree if and only if it is connected.
- A connected graph may have many spanning trees; the complete graph Kₙ has n^(n−2) of them (Cayley).
- A tree has a unique spanning tree, itself.

Finding one: depth-first search or breadth-first search, or by removing an edge from each cycle in turn.

**Minimum spanning tree (MST):** in a weighted graph, the spanning tree of least total weight.
- **Kruskal:** sort edges by weight, add the smallest edge that does not form a cycle, until n − 1 edges are chosen.
- **Prim:** start from a vertex and repeatedly add the cheapest edge from the tree to a new vertex.

Example: triangle a, b, c with edges ab = 1, bc = 2, ca = 3 has three spanning trees (any two edges); the MST is {ab, bc} with weight 3.

Applications: laying cable, pipelines or roads at least cost, network broadcasting and spanning-tree protocol, clustering.

## 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 n vertices has how many edges?
   A. n
   B. n + 1
   C. n/2
   D. n - 1
   Answer: D. Every tree on n vertices has n - 1 edges, and a spanning tree includes all n vertices. (Key point: Edges)

2. A graph has a spanning tree if and only if it is:
   A. Connected
   B. Acyclic
   C. Complete
   D. Planar
   Answer: A. Only a connected graph can have a subtree reaching all vertices. (Key point: Existence)

3. Kruskal's algorithm picks edges by:
   A. Largest weight first
   B. Smallest weight first, skipping any that form a cycle
   C. Cheapest edge from the current tree to a new vertex
   D. Random edges until connected
   Answer: B. Kruskal sorts edges and adds the cheapest that does not form a cycle until n - 1 are chosen. The cheapest-edge-from-tree rule describes Prim. (Key point: Kruskal)

4. Triangle with ab = 1, bc = 2, ca = 3: what is the MST weight?
   A. 4
   B. 5
   C. 3
   D. 6
   Answer: C. Take the two cheapest edges ab and bc: 1 + 2 = 3. (Key point: Example)

## Related in Discrete Structure

- [Short note: Spanning tree and applications](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aspanning-tree-and-applications) — Discrete Structure, chapter 4
- [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
- [Correlation: tree circumference and height](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Atrees-circumference-height-correlation) — Probability and Statistics, chapter 5