Lesson 1 of 8 · 14 min

Trees and spanning trees

Recognise trees and spanning trees, explain why a tree with vv vertices has v−1v - 1 edges, and find the spanning trees of a small graph.

What you will be able to do

  • Explain what a tree, a spanning tree and a minimum spanning tree are.
  • Decide whether a graph or subgraph is a tree, and whether it is a spanning tree.
  • Use the fact that a tree with vv vertices has v−1v - 1 edges.
  • Find how many edges must be removed from a connected graph to leave a spanning tree.

A farmer near Gatton wants to pipe water from a dam to four troughs. Every trough must be connected to the dam, but any pipe that forms a loop is wasted: the water could already get there another way.

A network that joins everything with no loops has a name — a tree — and it is the shape behind every "connect everything as cheaply as possible" problem in this topic.

Definition

Tree

A tree is a connected graph with no cycles. In a tree there is exactly one path between any two vertices.

Definition

Spanning tree

A spanning tree of a connected graph is a subgraph that

  • includes every vertex of the graph, and
  • is a tree: connected, with no cycles.

Most graphs have many different spanning trees.

Graph GG and three of its subgraphs. Which one is a spanning tree of GG?

In the figure, which subgraph is a spanning tree of GG?

Choose one answer

Count the edges in subgraph (1): 3 edges for 4 vertices. That is no accident. Start with the vertices and no edges, then add edges one at a time to join them up without making a cycle. Each new edge joins one more vertex to the rest, so joining vv vertices takes exactly v−1v - 1 edges. One fewer and the graph falls into two pieces; one more and it must contain a cycle.

Key idea

Edges in a tree

A tree with vv vertices has exactly v−1v - 1 edges.

So every spanning tree of a connected graph with vv vertices has v−1v - 1 edges, and to turn a graph with ee edges into a spanning tree you remove e−(v−1)e - (v - 1) of them.

Interactive

A tree of water pipes

Dam AA supplies troughs BB to GG. Count the vertices and edges, then press vertices to build a path between any two troughs — there is only ever one way to go. The Euler's formula panel shows a tree drawn on paper has just one face.

The same fact from Euler's formula

A tree has no cycles, so when you draw it there are no enclosed regions: the only face is the outside one, f=1f = 1. Euler's formula from Graphs and networks gives

v+1−e=2⇒e=v−1.v + 1 - e = 2 \quad\Rightarrow\quad e = v - 1.

Worked example

Counting the spanning trees of a small graph

  • Complex familiar
  • Technology free

Graph GG has vertices AA, BB, CC and DD and five edges: ABAB, BCBC, CDCD, DADA and the diagonal ACAC.

(a) How many edges does a spanning tree of GG have?

(b) How many edges must be removed from GG to leave a spanning tree?

(c) How many different spanning trees does GG have?

5 steps

Try it yourself first, then check the working one step at a time.

Method

  1. A spanning tree of a graph with vv vertices has v−1v - 1 edges.

  2. To count spanning trees of a small graph, list every set of v−1v - 1 edges and cross out those containing a cycle.

Watch out for

  • Forgetting that a spanning tree must include DD: the subgraph ABAB, BCBC, ACAC has 3 edges but is a cycle and misses DD.

A connected graph has 10 vertices and 15 edges. How many edges must be removed to leave a spanning tree?

Common mistake

Removing edges carelessly

Removing e−(v−1)e - (v - 1) edges does not guarantee a spanning tree. Each edge you remove must break a cycle. Remove a bridge and the graph falls apart, even if the count is right.

Which statement about a tree is false?

Choose one answer

In a weighted graph, different spanning trees have different total weights. The weight of a spanning tree is the sum of the weights of its edges, and a minimum spanning tree is a spanning tree with the least possible weight. Finding one is the subject of the next lesson.

Definition

Minimum spanning tree

A minimum spanning tree of a weighted connected graph is a spanning tree whose total weight is as small as possible. When some edges have equal weights, a graph can have more than one.

Summary

  • A tree is a connected graph with no cycles; there is exactly one path between any two of its vertices.

  • A spanning tree includes every vertex of a connected graph and is a tree.

  • A tree with vv vertices has v−1v - 1 edges, so remove e−(v−1)e - (v - 1) edges, each one breaking a cycle, to leave a spanning tree.

  • A minimum spanning tree is a spanning tree with the least total weight.

Finished the lesson?

Try the 3 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 1 of 80% read

Save your progress with a free account