Graph theory
Lesson 9 of 10
Trees and spanning trees
Objective. Recognise trees and build a minimum spanning tree.
The key idea
A tree is connected with no cycles and has exactly n − 1 edges. Kruskal's algorithm adds the cheapest edge that creates no cycle until all vertices connect.
Worked example
A connected graph has 6 vertices. How many edges in a spanning tree?
- 1A tree on n vertices has n − 1 edges.
- 26 − 1 = 5.
Answer: 5 edges
Practice
Each question comes with a picture and a listen button. Try it first, then reveal the answer.
Common mistake. Choosing the cheapest edge even when it closes a cycle.
Your progress
Tick each step as you finish it — Continue brings you back here.
0 of 5 steps complete