Lesson 1: Trees and spanning trees
Counting the spanning trees of a small graph
SkillTrees and spanning trees
Worked example
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.
Answer
(a) 3 edges. (b) 2 edges. (c) has 8 different spanning trees.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
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 .