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₄ ✓.