Mathematics Standard • Year 12 • Module 5 • Lesson 3
Paths, Trails and Cycles — Problem Set
Apply the routes vocabulary and counting strategies to realistic Australian contexts: bushwalking trails, ride-share routing, mall layouts and maze design.
Problem 1 — Bushwalk in the Blue Mountains
A national-park map shows 5 lookouts: Echo Point (E), Three Sisters (T), Katoomba Falls (K), Wentworth Falls (W), Leura Cascades (L). Trails exist between: E–T, T–K, K–W, K–L, W–L, E–L.
Set up: What are we solving for?
(i) Is the network connected? Justify in one sentence. 1 mark
(ii) Find all paths from Echo Point (E) to Wentworth Falls (W). 2 marks
(iii) A walker insists on a route starting and finishing at E that visits Three Sisters at least once and never re-uses a trail. Give one such trail and state whether it is a closed trail (circuit) or just an open trail. 2 marks
Stuck? Revisit lesson § Card 02 — Finding All Paths (systematic branching).Problem 2 — Ride-share network in Melbourne
A driver works between 4 pickup zones — Carlton (C), Brunswick (B), Northcote (N), Fitzroy (F). The road map (one-way streets ignored) is K₄ minus one edge: all pairs are joined except B–N.
Set up: What are we solving for?
(i) List the edges of the network. 1 mark
(ii) Find all paths from B to N. 2 marks
(iii) The driver wants to make a 4-zone cycle (visit every zone, return to start). Find one such cycle and state whether the network has a 3-edge cycle (triangle). 2 marks
Stuck? Revisit lesson § Card 03 — connectedness and cycles.Problem 3 — Westfield shopping centre layout
A new Westfield in Parramatta has 6 zones connected by walkways: Food court (F), Cinema (C), Fashion (M), Tech (T), Supermarket (S), Carpark (P). Walkways: F–C, F–M, F–S, C–T, M–T, M–S, S–P.
Set up: What are we solving for?
(i) Find the shortest path (fewest walkways) from the Carpark (P) to the Tech zone (T). 2 marks
(ii) Find all paths from the Carpark (P) to the Cinema (C). 2 marks
(iii) Identify any cycle in the network. (Hint: F is connected to both M and S, and M is connected to S.) 1 mark
Stuck? Sketch the network first — triangles are the easiest cycles to spot.Problem 4 — Telecommunications islands
After a storm, two regional NSW telecommunications networks lose their interconnecting cable. The remaining links are: Tamworth (T) – Armidale (A) – Glen Innes (G); and Coffs Harbour (C) – Grafton (R) – Lismore (L) – Byron Bay (Y), with the cycle C–R–L–Y–C.
Set up: What are we solving for?
(i) Sketch the network. State how many connected components it has. 2 marks
(ii) Is there a path from Tamworth (T) to Coffs Harbour (C)? Justify. 1 mark
(iii) The repair team can install ONE new cable between any town in the first component and any town in the second. Which single cable would minimise the longest "any-to-any" path (the network "diameter")? State the new path from T to Y after your chosen install and justify your choice. 3 marks
Stuck? Choose the cable that connects a "middle" town in each component (A or R), not an endpoint.Problem 5 — School fete maze
The school fete maze has 7 rooms R₁…R₇ with doors: R₁–R₂, R₁–R₃, R₂–R₃, R₂–R₄, R₃–R₅, R₄–R₅, R₄–R₆, R₅–R₇, R₆–R₇.
Set up: What are we solving for?
(i) Find the shortest path (in number of doors) from the entrance R₁ to the exit R₇. 2 marks
(ii) Find any cycle (closed path that visits each room at most once except for start = end) that passes through R₄. 2 marks
(iii) A maze-runner says, "I went R₁ → R₂ → R₃ → R₁ → R₃ → R₅ → R₇." Decide whether this route is a walk, trail or path, and explain in one sentence. 2 marks
Stuck? Check whether each edge in the runner's route appears more than once.How did this worksheet feel?
What I'll revisit before next class:
Problem 1 — Blue Mountains bushwalk
Set up. We are checking connectivity, enumerating paths E → W, and finding a closed route through T.
(i) Yes, connected — every lookout reachable (e.g. T from E, K from T, W and L from K).
(ii) Paths from E to W:
— E–T–K–W
— E–T–K–L–W
— E–L–W
— E–L–K–W
— E–T–K–L–W (already listed). 4 distinct paths.
(iii) Example closed trail through T starting/ending at E: E–T–K–L–E. Uses edges ET, TK, KL, LE (all distinct). Since start = end and no edge repeats, this is a closed trail (circuit).
Problem 2 — Ride-share zones
Set up. We list edges of K₄ minus B–N, enumerate paths B → N, find a 4-cycle and check for triangles.
(i) Edges: C–B, C–N, C–F, B–F, N–F. (K₄ has 6 edges; removing B–N gives 5.)
(ii) Paths B → N:
— B–C–N
— B–F–N
— B–C–F–N
— B–F–C–N
4 paths.
(iii) 4-cycle: B–C–N–F–B (uses BC, CN, NF, FB). Triangles in K₄ minus BN: B–C–F–B (yes, BC, CF, FB), N–C–F–N (yes, NC, CF, FN). Yes, the network contains 3-edge cycles.
Problem 3 — Westfield walkways
Set up. We sketch the layout, find shortest P → T, enumerate P → C, and spot any cycle.
(i) P only connects to S. S → M, F. M → T. So P–S–M–T is 3 walkways. (P–S–F–C–T is 4.) Shortest: P–S–M–T (3 walkways).
(ii) Paths from P to C: P–S–F–C; P–S–M–T–C; P–S–M–F–C; P–S–F–M–T–C; P–S–M–F–? — F to C direct works. 3 distinct shortest paths: P–S–F–C (3 edges); P–S–M–T–C (4 edges); P–S–M–F–C (4 edges). Markers should accept any reasonable enumeration provided no revisited vertices.
(iii) Cycle: F–M–S–F (uses FM, MS, SF). Other cycles: C–T–M–F–C (4-edge), etc.
Problem 4 — Disconnected telecom network
Set up. We sketch components, check T-to-C path, and reason about an optimal connecting cable.
(i) Two components: {T, A, G} (a path T–A–G) and {C, R, L, Y} (cycle C–R–L–Y–C). 2 components.
(ii) No path — T and C are in different components, so no edge sequence connects them.
(iii) To minimise the diameter, connect "central" vertices (A in component 1, R in component 2). With the new cable A–R, the path T → Y is T–A–R–L–Y or T–A–R–Y (4 edges; if the new cable is A–R, path T–A–R–Y uses TA, AR, RY = 3 edges). Alternative installs (e.g. T–C, G–Y) create longer diameters. Recommendation: install A–R so the longest T-to-anywhere path is at most 4 edges, balancing both sides.
Problem 5 — Fete maze
Set up. Shortest R₁ → R₇, a cycle through R₄, and classifying a given route.
(i) R₁–R₂–R₄–R₆–R₇ is 4 doors. R₁–R₃–R₅–R₇ is 3 doors. Shortest: R₁–R₃–R₅–R₇ (3 doors).
(ii) Cycle through R₄: R₄–R₅–R₇–R₆–R₄ (uses R₄R₅, R₅R₇, R₇R₆, R₆R₄ — all exist, no other vertex repeats).
(iii) Edges used in R₁–R₂–R₃–R₁–R₃–R₅–R₇: R₁R₂, R₂R₃, R₃R₁, R₁R₃ (repeat!), R₃R₅, R₅R₇. Edge R₁R₃ is reused ⇒ walk only, not a trail. (Vertex R₃ also repeats, but the edge-repeat is what disqualifies it from being a trail.)