Trees, spanning trees, and counting them

Mathematics · Discrete Mathematics · ages 20-21

Name ______________________ Date ____________

A tree has 9 vertices. How many edges does it have? Give a number.
Answer: ______________
A tree has 9 vertices. How many edges does it have?
Answer: ______________
A connected graph with exactly one path between every two vertices is a tree.
Circle one: True False
Which of these CANNOT be a tree?
- 6 vertices with 6 edges
- 6 vertices with 5 edges
- 1 vertex with 0 edges
A connected graph has 7 vertices. How many edges does any spanning tree of it have?
- 6
- 7
- 8
- 21
You add one missing edge to a tree. What happens?
- The graph disconnects
- Nothing changes at all
- Exactly one cycle closes
How many labelled trees are there on 4 vertices?
Answer: ______________
How many labelled trees are there on 4 vertices? Give a number.
Answer: ______________
How many labelled trees are there on 5 vertices?
Answer: ______________
How many labelled trees are there on 5 vertices? Give a number.
Answer: ______________

Answer key

For grown-ups. Fold this page away before handing over the rest.

8 · A tree on n vertices always has n minus 1 edges: 9 minus 1 = 8.
8 · A tree on n vertices always has n minus 1 edges.
True · Connected plus unique paths is one of the equivalent definitions.
6 vertices with 6 edges · A tree needs exactly vertices minus 1 edges, and 6 is not 5.
6 · A spanning tree keeps all 7 vertices and needs exactly 7 minus 1 = 6 edges.
Exactly one cycle closes · Its ends already join by one path, so the new edge completes one cycle.
16 · Cayley gives 4 to the power (4 minus 2), which is 16.
16 · Cayley gives 4 to the power (4 minus 2) = 4 squared = 16.
125 · Cayley gives 5 to the power 3, which is 125.
125 · Cayley gives 5 to the power (5 minus 2) = 5 cubed = 125.