Mathematics Standard • Year 12 • Module 5 • Lesson 6
Trees and Spanning Trees — Problem Set
Apply trees and spanning trees to realistic Australian contexts: NBN cable rollouts, family trees, organisational charts and computer networks.
Problem 1 — NBN fibre rollout to 6 homes
An NBN technician plans the fibre connections for 6 homes H₁…H₆ in a new estate. Possible cable runs: H₁–H₂, H₁–H₃, H₂–H₃, H₂–H₄, H₃–H₅, H₄–H₅, H₄–H₆, H₅–H₆.
Set up: What are we solving for?
(i) How many cable runs are needed for a spanning tree (every home connected, no loops)? 2 marks
(ii) Find one valid spanning tree (list its edges). 2 marks
(iii) Explain in one sentence why the company prefers a spanning tree over the full network of 8 cable runs. 1 mark
Stuck? Revisit lesson § Card 02 — spanning trees are the minimal connected sub-network.Problem 2 — Family tree of 7 cousins
A family tree shows 7 cousins C₁…C₇ all descended from a single ancestor at the top. Each cousin has exactly one parent edge upward (forming a tree).
Set up: What are we solving for?
(i) Including the ancestor, how many vertices are in the family tree? 1 mark
(ii) How many parent–child edges does the tree contain? 2 marks
(iii) Suppose a researcher discovers an additional connection (a marriage) between two cousins, creating a new edge. Is the resulting network still a tree? Explain in one sentence. 2 marks
Stuck? Adding ANY edge to a tree creates exactly one cycle.Problem 3 — Company organisational chart
A small Brisbane company has 1 CEO, 3 directors, and 8 staff (CEO → directors, each director → 2 or 3 staff). The reporting structure forms a tree.
Set up: What are we solving for?
(i) How many vertices and how many edges does the org chart have? Justify using the tree formula. 2 marks
(ii) How many leaves (vertices with degree 1) does the tree have? 2 marks
(iii) The CEO reorganises so that the 3 directors also report to each other in a triangle (3 new edges among directors). Is the new network still a tree? Explain. 2 marks
Stuck? A leaf is a vertex with only one edge. The CEO has degree 3 (one to each director). Each staff member reports to one director only.Problem 4 — Office computer network
An office has 5 computers connected by Ethernet cables in K₅ (every pair connected). Cayley's formula says K₅ has 5³ = 125 spanning trees.
Set up: What are we solving for?
(i) How many edges in K₅? How many edges in any spanning tree of K₅? How many edges must be "switched off" to leave a spanning tree active? 2 marks
(ii) Give 3 distinct spanning trees of K₅ on vertices A, B, C, D, E. 2 marks
(iii) Use Cayley's formula to compute the number of spanning trees of K₆. 1 mark
Stuck? Cayley: number of spanning trees of Kₙ = n^(n − 2). For K₆: 6⁴.Problem 5 — Street-lighting rewiring
A council is rewiring street lighting along 7 intersections I₁…I₇ in a regional NSW town. The available conduit network is: I₁–I₂, I₁–I₃, I₂–I₃, I₂–I₄, I₃–I₅, I₄–I₅, I₄–I₆, I₅–I₇, I₆–I₇.
Set up: What are we solving for?
(i) How many edges in the original network? How many in any spanning tree? 2 marks
(ii) The electrician proposes the spanning tree {I₁–I₂, I₂–I₃, I₂–I₄, I₃–I₅, I₄–I₆, I₅–I₇}. (a) Verify the edge count. (b) Check that every intersection is reachable. 2 marks
(iii) One conduit (I₄–I₆) is damaged and unusable. Find an alternative spanning tree that does NOT use I₄–I₆. List its edges and confirm both the edge count and connectedness. 3 marks
Stuck? Remove a different edge from a cycle that includes I₄–I₆; replace I₄–I₆ with another edge that reconnects I₆.How did this worksheet feel?
What I'll revisit before next class:
Problem 1 — NBN fibre rollout
Set up. We compute n − 1 for the spanning tree edge count, find one valid tree, and explain the cost benefit.
(i) Spanning tree on 6 homes needs 6 − 1 = 5 cable runs.
(ii) Example spanning tree: H₁–H₂, H₂–H₄, H₄–H₆, H₄–H₅, H₃–H₅ (5 edges; every home reachable; no cycles). Many other valid spanning trees exist.
(iii) A spanning tree uses the minimum cable (5 runs vs 8), keeps every home connected, and saves both cable and installation cost — every extra cable would create redundancy that is unnecessary for basic connectivity.
Problem 2 — Family tree of 7 cousins
Set up. Count vertices, count tree edges, then test what happens when a non-tree edge is added.
(i) 7 cousins + 1 ancestor = 8 vertices.
(ii) A tree on 8 vertices has 8 − 1 = 7 edges.
(iii) No — adding any edge to a tree creates exactly one cycle, so the new network is no longer acyclic and therefore not a tree.
Problem 3 — Company org chart
Set up. Vertices count, tree edges via n − 1, count leaves, then test what happens when 3 director-to-director edges are added.
(i) 1 CEO + 3 directors + 8 staff = 12 vertices. Tree edges = 12 − 1 = 11 edges (3 CEO-to-director + 8 director-to-staff).
(ii) Leaves (degree 1) = the 8 staff members (each reports to exactly one director). The CEO has degree 3 (to each director), so not a leaf. Directors each have degree ≥ 2 (one up to CEO + 2 or 3 down to staff). 8 leaves.
(iii) No — adding the 3 new edges among the directors creates a triangle (a cycle). A tree cannot contain any cycle, so the new network is not a tree.
Problem 4 — K₅ office network
Set up. Count K₅ edges, count spanning-tree edges, write down 3 example trees, apply Cayley for K₆.
(i) K₅ has 5 × 4 ÷ 2 = 10 edges. Spanning tree has 5 − 1 = 4 edges. "Switch off" 10 − 4 = 6 edges.
(ii) Three spanning trees of K₅:
— Path: A–B–C–D–E (edges AB, BC, CD, DE).
— Star centred at A: edges AB, AC, AD, AE.
— Mixed: edges AB, BC, BD, BE (star centred at B).
(iii) Cayley for K₆: n^(n − 2) = 6⁴ = 1296 spanning trees.
Problem 5 — Street-lighting rewiring
Set up. Count edges, verify the proposed spanning tree, then construct an alternative without I₄–I₆.
(i) Original network has 9 edges (listed). Spanning tree on 7 intersections has 7 − 1 = 6 edges.
(ii) Proposed tree edges: I₁–I₂, I₂–I₃, I₂–I₄, I₃–I₅, I₄–I₆, I₅–I₇ — that's 6 edges ✓. Reachability: from I₁ → I₂ → I₃ → I₅ → I₇; I₁ → I₂ → I₄ → I₆. All 7 intersections reachable from I₁ ✓.
(iii) Remove I₄–I₆ (the damaged conduit). We need a replacement edge that connects I₆ back into the rest. Options: I₆–I₇ (since I₅–I₇ is already in the tree, adding I₆–I₇ keeps it connected). So alternative spanning tree: {I₁–I₂, I₂–I₃, I₂–I₄, I₃–I₅, I₅–I₇, I₆–I₇} — 6 edges ✓; reachable from I₁: I₁ → I₂ → I₃ → I₅ → I₇ → I₆, and I₁ → I₂ → I₄ ✓.