Skip to main content
MathidiaMathematics Academy
Discrete mathematics
Lesson 49 of 75
Challenge

Trees and spanning trees

Objective. Characterise trees and construct spanning trees.

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

Learn: the key idea

A tree is a connected graph with no cycles, and a key characterisation is that a graph with n vertices is a tree if and only if it is connected and has exactly n − 1 edges, or equivalently is acyclic with n − 1 edges. A spanning tree of a connected graph G is a subgraph that includes every vertex of G, uses only edges from G, and forms a tree, effectively connecting all vertices with the minimum possible number of edges and no redundant cycles. Algorithms such as Kruskal's build a spanning tree by repeatedly adding the cheapest edge that does not create a cycle, continuing until n − 1 edges have been chosen. For a connected graph with 6 vertices, every spanning tree must contain exactly 5 edges regardless of how many total edges the original graph has.

Worked example

A connected graph has 9 vertices. State the number of edges that any spanning tree of this graph must contain.

9
Coordinate grid with the line 9
  1. 1Recall the key tree property: a tree with n vertices has exactly n − 1 edges.
  2. 2Identify that a spanning tree includes all vertices of the original graph.
  3. 3Substitute n = 9 into the formula n − 1.
  4. 4Compute the result to state the edge count.

Answer: 8 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. Students assume removing any edge from a cycle always leaves a valid spanning tree, but if the graph has multiple disjoint cycles sharing no vertex, removing edges from only one cycle may not touch the others.

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