Mathematics Standard • Year 12 • Module 5 • Lesson 6
Trees and Spanning Trees — Skill Drill
Build fluency in identifying trees, applying the n − 1 edge rule, and finding spanning trees by removing edges from cycles.
1. Quick recall
Answer each question in the space provided. 1 mark each
Q1.1 Complete the definitions:
A tree is a __________ network with __________ cycles.
A spanning tree is a tree that includes __________ vertex of the original network.
Q1.2 The number of edges in a tree with n vertices is exactly __________.
Q1.3 A leaf is a vertex with degree __________.
2. Worked example — find a spanning tree
Problem. A connected network has 5 vertices A, B, C, D, E and 7 edges: AB, AC, BC, BD, CD, CE, DE. Find a spanning tree.
Step 1 — Count vertices and edges.
n = 5 vertices, edges = 7
Step 2 — Calculate how many edges to remove.
A spanning tree has n − 1 = 4 edges. Remove 7 − 4 = 3 edges.
Step 3 — Identify cycles and break them.
Cycle 1: A–B–C–A. Remove BC.
Cycle 2: B–D–C–B (with BC gone, check: B–D–C is a path; is there still a cycle? Edges left so far: AB, AC, BD, CD, CE, DE — still has cycle B–D–C–A–B via AC and AB. Remove CD.
Cycle 3: After removing CD, edges left: AB, AC, BD, CE, DE. Still has cycle C–E–D–B–A–C via AC. Remove DE.
Step 4 — Check the result.
Remaining edges: AB, AC, BD, CE. Count = 4 = n − 1 ✓. Connected (every vertex reachable from A). No cycles ✓.
Conclusion. One valid spanning tree: AB, AC, BD, CE. (Many other spanning trees exist — any 4 edges that keep the network connected and acyclic.)
3. Faded example — fill in the missing steps
A connected network has 6 vertices and 8 edges. Find how many edges to remove and verify with the tree formula. 4 marks
Step 1 — Tree formula: spanning tree has ____ − 1 = ____ edges.
Step 2 — Edges to remove: ____ − ____ = ____ edges.
Step 3 — Constraint: the edges removed must each lie on a __________ (cycle/tree/leaf) so the result stays __________.
Conclusion. Remove ____ edges to form a spanning tree; final edge count = ____.
4. Graduated practice — trees and spanning trees
Foundation — single-step facts (4 questions)
| Q | Problem | Answer |
|---|---|---|
| 4.1 1 | How many edges in a tree with 11 vertices? | |
| 4.2 1 | A connected network has 6 vertices and 5 edges. Is it a tree? (Yes / No.) | |
| 4.3 1 | How many spanning trees does K₃ (triangle) have? (Use Cayley's formula nⁿ⁻².) | |
| 4.4 1 | True or false: every connected network has at least one spanning tree. |
Standard — typical HSC difficulty (6 questions)
4.5 A tree has 8 vertices. (a) How many edges? (b) Add one more edge anywhere — how many cycles does the new network have? 2 marks
4.6 A connected network has 9 vertices and 13 edges. How many edges must be removed to form a spanning tree? 2 marks
4.7 Triangle ABC plus a pendant vertex D connected only to A. (a) How many vertices and edges? (b) Find a spanning tree by removing the right number of edges. 2 marks
4.8 A square ABCD with one diagonal AC has 5 edges. List all 3 spanning trees by stating which single edge to remove from each cycle. 2 marks
4.9 Use Cayley's formula nⁿ⁻² to compute the number of spanning trees of (a) K₄ and (b) K₅. 2 marks
4.10 Identify which of these networks are trees: (a) Path A–B–C–D. (b) Star with centre O and 4 outer vertices. (c) Square ABCD. (d) Triangle ABC. 2 marks
Extension — combine ideas (2 questions)
4.11 A network has 6 vertices with degree sequence 1, 1, 2, 2, 2, 2. (a) Use the handshaking lemma to find the number of edges. (b) State whether this network could be a tree, and justify. 3 marks
4.12 A connected network has 5 vertices and edges AB, BC, CD, DE, AE, AC. (a) How many edges must be removed to form a spanning tree? (b) Find one valid spanning tree by listing its edges. 3 marks
5. Self-check the easy 3
Tick the first three once you've checked your method works.
How did this worksheet feel?
What I'll revisit before next class:
Q1.1 — Definitions
Tree: connected network with no cycles. Spanning tree: a tree that includes every vertex of the original network.
Q1.2 — Edge count
Exactly n − 1 edges.
Q1.3 — Leaf
A leaf is a vertex with degree 1.
Q3 — Faded example (6 vertices, 8 edges)
Step 1: Spanning tree has 6 − 1 = 5 edges.
Step 2: Remove 8 − 5 = 3 edges.
Step 3: Each removed edge must lie on a cycle so the result stays connected.
Conclusion: Remove 3 edges to form a spanning tree; final edge count = 5.
Q4.1 — Tree, 11 vertices
11 − 1 = 10 edges.
Q4.2 — 6 vertices, 5 edges, connected
Yes — connected with exactly n − 1 = 5 edges, so it is a tree (no cycles possible).
Q4.3 — Spanning trees of K₃
Cayley: 3³⁻² = 3¹ = 3 spanning trees (remove one of the 3 edges from the triangle).
Q4.4 — Every connected network has a spanning tree?
True. Keep removing edges from cycles until no cycles remain — the network stays connected (because the removed edges were on cycles, so alternative paths existed).
Q4.5 — Tree on 8 vertices
(a) 8 − 1 = 7 edges. (b) Adding any edge to a tree creates exactly 1 cycle.
Q4.6 — 9 vertices, 13 edges
Spanning tree needs 9 − 1 = 8 edges. Remove 13 − 8 = 5 edges.
Q4.7 — Triangle ABC + pendant D on A
(a) 4 vertices, 4 edges (AB, BC, CA, AD).
(b) Spanning tree needs 4 − 1 = 3 edges. Remove one edge from the triangle. Three valid spanning trees: {BC, CA, AD}, {AB, CA, AD}, {AB, BC, AD}.
Q4.8 — Square ABCD with diagonal AC
Edges: AB, BC, CD, DA, AC. Cycles: A–B–C–A (triangle 1), A–C–D–A (triangle 2), A–B–C–D–A (the square). Need to break enough cycles. Spanning tree has 4 − 1 = 3 edges, so remove 2 edges total. Three example spanning trees:
— Remove AB and CD ⇒ {BC, DA, AC}
— Remove BC and DA ⇒ {AB, CD, AC}
— Remove AB and DA ⇒ {BC, CD, AC}
— Remove BC and CD ⇒ {AB, DA, AC}
— Remove AC and AB ⇒ {BC, CD, DA}
— Remove AC and CD ⇒ {AB, BC, DA}
— Remove AC and DA ⇒ {AB, BC, CD}
— Remove AC and BC ⇒ {AB, CD, DA}
(Markers should accept any 3 valid spanning trees — the question only asks for "the 3 spanning trees" via single-edge removal from each named cycle, but with 5 edges there are actually more.) One way to list "three spanning trees by removing one edge from a cycle": remove AB (from triangle ABC), remove BC (from triangle ABC), or remove CD (from triangle ACD).
Q4.9 — Cayley
(a) K₄: 4² = 16 spanning trees. (b) K₅: 5³ = 125 spanning trees.
Q4.10 — Which are trees?
(a) Path A–B–C–D: tree ✓ (connected, no cycles). (b) Star: tree ✓. (c) Square: not a tree (contains cycle). (d) Triangle: not a tree (contains cycle).
Q4.11 — Degree sequence 1, 1, 2, 2, 2, 2
(a) Sum = 1+1+2+2+2+2 = 10. Edges = 10 ÷ 2 = 5.
(b) n = 6 vertices, edges = 5 = n − 1 ⇒ could be a tree if connected. Indeed, this is the degree sequence of a path (two endpoints of degree 1, four internal vertices of degree 2): A–B–C–D–E–F is one valid tree with this degree sequence.
Q4.12 — 5 vertices, 6 edges (pentagon + diagonal)
(a) Spanning tree needs 5 − 1 = 4 edges. Remove 6 − 4 = 2 edges.
(b) Edges given: AB, BC, CD, DE, AE, AC. Cycles: A–B–C–A (triangle) and A–C–D–E–A (4-cycle). One spanning tree: remove AC (breaks both cycles) and one more edge from any remaining cycle — but removing AC alone breaks both cycles, leaving 5 edges. We need to remove 2 edges total, so remove AC and one of AB, BC, CD, DE, AE. E.g., remove AC and BC ⇒ spanning tree edges: AB, CD, DE, AE. Verify: 4 edges, connected (A–B, A–E, D–E, C–D form a path-like structure), no cycles ✓.