Lesson 1 of 8 · 14 min
Trees and spanning trees
Recognise trees and spanning trees, explain why a tree with vertices has 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 vertices has 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 and three of its subgraphs. Which one is a spanning tree of ?
In the figure, which subgraph is a spanning tree of ?
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 vertices takes exactly 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 vertices has exactly edges.
So every spanning tree of a connected graph with vertices has edges, and to turn a graph with edges into a spanning tree you remove of them.
Dam supplies troughs to . 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, . Euler's formula from Graphs and networks gives
Worked example
Counting the spanning trees of a small graph
Graph has vertices , , and and five edges: , , , and the diagonal .
(a) How many edges does a spanning tree of have?
(b) How many edges must be removed from to leave a spanning tree?
(c) How many different spanning trees does have?
Step 1: Use the edge count of a tree
has vertices, so every spanning tree has edges.
Step 2: Find how many edges go
has 5 edges, so remove of them.
Step 3: Count every choice of 3 edges
Choosing 3 of the 5 edges can be done in 10 ways: , , , , , , , , , .
Listing in a fixed order (always start with the earliest edge you have not used up) makes sure you miss none and repeat none.
Step 4: Cross out the choices with a cycle
Three edges can only form a cycle if they make a triangle. has two triangles: and . Cross out those two.
3 edges on 4 vertices with no cycle are automatically connected, so every remaining choice is a spanning tree.
Step 5: Count what is left
spanning trees.
Try it yourself first, then check the working one step at a time.
Answer
(a) 3 edges. (b) 2 edges. (c) has 8 different spanning trees.
Method
A spanning tree of a graph with vertices has edges.
To count spanning trees of a small graph, list every set of edges and cross out those containing a cycle.
Watch out for
Forgetting that a spanning tree must include : the subgraph , , has 3 edges but is a cycle and misses .
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 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?
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 vertices has edges, so remove 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.