Mathematics Standard • Year 12 • Module 5 • Lesson 6
Trees and Spanning Trees — Past-Paper Style
Practise HSC Mathematics Standard 2 short-answer and extended-response writing on trees and spanning trees.
1. Short-answer questions
1.1 A tree has 15 vertices. Find the number of edges and explain in one line why this must be the case. 2 marks Band 3
1.2 A connected network has 10 vertices and 14 edges.
(a) Find the number of edges that must be removed to form a spanning tree.
(b) State in one sentence the rule for choosing which edges to remove. 3 marks Band 3-4
1.3 A network has vertices A, B, C, D, E with edges AB, AC, BC, BD, CD, CE, DE.
(a) Find a spanning tree by listing its edges.
(b) State the number of edges removed.
(c) Explain in one sentence why removing edges from cycles (rather than from non-cycle "bridge" edges) preserves connectedness. 4 marks Band 4
2. Extended response
2.1 A council water-supply engineer must design a network connecting 6 reservoirs R₁…R₆ in a regional NSW district. The available pipeline routes (each with a fixed construction cost) form the network:
R₁–R₂, R₁–R₃, R₂–R₃, R₂–R₄, R₃–R₄, R₃–R₅, R₄–R₅, R₄–R₆, R₅–R₆.
(a) State the number of vertices and edges in the original network, and the number of edges in any spanning tree of this network.
(b) Find one valid spanning tree by listing its 5 edges. Verify that every reservoir is connected (reachable from R₁) and that the tree contains no cycles.
(c) The engineer realises that pipeline R₄–R₆ must be excluded for environmental reasons. Find a new spanning tree that does NOT include R₄–R₆. List its edges, justify why it is a valid spanning tree (correct number of edges + connected + no cycles), and write a one-sentence conclusion explaining how the engineer can guarantee R₆ remains connected. 7 marks Band 5-6
Explicit marking criteria
Part (a) — 2 marks
• 1 mark — correctly states 6 vertices and 9 edges.
• 1 mark — spanning tree has 6 − 1 = 5 edges (formula explicit).
Part (b) — 2 marks
• 1 mark — lists a valid 5-edge spanning tree.
• 1 mark — explicit reachability check from R₁ and statement of no cycles.
Part (c) — 3 marks
• 1 mark — proposes spanning tree NOT using R₄–R₆.
• 1 mark — verifies count and connectedness.
• 1 mark — explicit conclusion sentence about R₆ connectivity (e.g., via R₅–R₆).
Your response:
Stuck on (c)? Without R₄–R₆, the only remaining edge to R₆ is R₅–R₆. So R₆ MUST be connected through R₅.How did this worksheet feel?
What I'll revisit before next class:
1.1 — Tree with 15 vertices (2 marks)
Sample response.
Edges = n − 1 = 15 − 1 = 14 edges. A tree is connected and acyclic; any connected network on n vertices with no cycles has exactly n − 1 edges.
Marking notes. 1 mark — correct number 14. 1 mark — explicit justification using "n − 1" or the tree property. A bare "14" with no justification scores 1/2.
1.2 — 10 vertices, 14 edges (3 marks)
Sample response.
(a) Spanning tree has n − 1 = 9 edges. Edges to remove = 14 − 9 = 5 edges.
(b) Each removed edge must lie on a cycle, so that the network remains connected (a cycle has alternative paths around it).
Marking notes. (a) 1 mark — 9 edges in tree; 1 mark — removes 5. (b) 1 mark — "remove from a cycle to preserve connectedness" rule.
1.3 — 5 vertices, 7 edges (4 marks)
Sample response.
(a) One valid spanning tree: {AB, AC, BD, CE}. (Or many other 4-edge trees that keep every vertex reachable and have no cycle, e.g. {AB, BC, CD, DE}.)
(b) Spanning tree has 4 edges, original has 7, so 3 edges removed.
(c) Removing an edge from a cycle preserves connectedness because the cycle provides an alternative path around the removed edge, so every pair of vertices that was connected before is still connected after the removal.
Marking notes. (a) 1 mark — valid spanning tree. (b) 1 mark — 3 edges removed. (c) 1 mark — "alternative path" explanation. 1 mark — overall coherence and edge verification (no cycles in the proposed tree).
2.1 — Water-supply network (7 marks): sample Band-6 response
Sample Band-6 response.
(a) Vertices, edges and spanning-tree edge count.
6 vertices (R₁, …, R₆) and 9 edges (R₁R₂, R₁R₃, R₂R₃, R₂R₄, R₃R₄, R₃R₅, R₄R₅, R₄R₆, R₅R₆). [1 mark.]
A spanning tree on 6 vertices has 6 − 1 = 5 edges. [1 mark — formula explicit.]
(b) Valid spanning tree using all routes.
Edges: {R₁–R₂, R₂–R₃, R₂–R₄, R₄–R₅, R₄–R₆}. 5 edges ✓. [1 mark — tree.]
Reachability from R₁: R₁ → R₂ → R₃; R₁ → R₂ → R₄ → R₅; R₁ → R₂ → R₄ → R₆. All 6 reservoirs reachable ✓. No cycles (each vertex has exactly one upward path to R₁). [1 mark — explicit verification.]
(c) Spanning tree without R₄–R₆.
Replace R₄–R₆ with R₅–R₆ so R₆ stays connected. New spanning tree: {R₁–R₂, R₂–R₃, R₂–R₄, R₃–R₅, R₅–R₆}. 5 edges ✓. [1 mark — proposes valid replacement tree.]
Reachability: R₁ → R₂ → R₃ → R₅ → R₆; R₁ → R₂ → R₄. All 6 reservoirs reachable ✓. No cycles (only 5 edges, and each new edge added to a tree creates exactly one cycle — but here we have exactly the tree's edge count). [1 mark — verifies count and connectedness.]
Conclusion: by replacing the excluded pipeline R₄–R₆ with R₅–R₆, the engineer guarantees R₆ remains connected through reservoir R₅ (via the route R₁ → R₂ → R₃ → R₅ → R₆), and the new design still uses the minimum 5 pipelines required for a spanning tree on 6 reservoirs. [1 mark — explicit conclusion about R₆ connectivity.]
Total: 7/7.
Band descriptors for marker.
Band 3: Counts vertices and edges; gives a spanning tree but doesn't verify connectedness or no-cycles. ≈ 3 marks.
Band 4: Vertices/edges/tree-edge count all correct; valid spanning tree in (b); attempts (c) but tree contains R₄–R₆ or fails edge count. ≈ 4-5 marks.
Band 5: All parts complete with replacement spanning tree; explicit reachability check; no conclusion sentence about R₆. ≈ 6 marks.
Band 6: Complete, with explicit conclusion sentence naming R₅–R₆ as the bridge to R₆ and the minimum-5-pipelines guarantee. 7/7.