Skip to main content
MathidiaMathematics Academy
Graph theory
Lesson 9 of 10
Standard practice

Trees and spanning trees

Objective. Recognise trees and build a minimum spanning tree.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: 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?

6
Coordinate grid with the line 6
  1. 1A tree on n vertices has n − 1 edges.
  2. 26 − 1 = 5.

Answer: 5 edges

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Choosing the cheapest edge even when it closes a cycle.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard