Mathematics Standard • Year 12 • Module 5 • Lesson 3
Paths, Trails and Cycles — Past-Paper Style
Practise HSC Mathematics Standard 2 short-answer and extended-response writing on paths, trails and cycles.
1. Short-answer questions
1.1 A network has vertices A, B, C, D, E and edges AB, AC, BC, BD, CE, DE. List the route A–B–C–B–D–E and classify it as walk, trail or path (use the strictest classification that applies). Justify your answer in one sentence. 2 marks Band 3
1.2 The diagram represents a small road network with edges AB, AC, BC, BD, CD, CE, DE.
(a) Find all paths from A to E.
(b) State the length (in edges) of the shortest path. 3 marks Band 3-4
1.3 A council park has 6 garden zones connected by paths: G₁–G₂, G₁–G₃, G₂–G₃, G₂–G₄, G₃–G₅, G₄–G₅, G₄–G₆, G₅–G₆.
(a) Determine whether the network contains any 3-edge cycle (triangle). If yes, list one.
(b) Determine whether the network is connected, and find a path of length 3 from G₁ to G₆.
(c) A walker claims a route G₁ → G₃ → G₂ → G₄ → G₅ → G₆ uses each garden exactly once. Verify this and state whether the route is a path. 4 marks Band 4
2. Extended response
2.1 A council in Cessnock is designing a 6-stop community shuttle bus route. The road network connecting the 6 stops S₁…S₆ is:
S₁–S₂, S₁–S₃, S₂–S₃, S₂–S₄, S₃–S₄, S₃–S₅, S₄–S₅, S₄–S₆, S₅–S₆.
(a) Determine whether the network is connected, and state the number of edges.
(b) Find all paths from S₁ to S₆. List them and state which is shortest (by number of edges).
(c) The council wants the shuttle to make a complete loop that starts and ends at S₁, visits every stop exactly once (a Hamiltonian-style cycle), and uses only existing roads. Find one such cycle if it exists, or prove no such cycle exists. Write a one-sentence conclusion. 7 marks Band 5-6
Explicit marking criteria
Part (a) — 2 marks
• 1 mark — correct edge count of 9.
• 1 mark — explicit "connected" statement with brief justification (e.g. every stop reachable from S₁).
Part (b) — 2 marks
• 1 mark — lists at least four distinct paths from S₁ to S₆.
• 1 mark — correctly identifies the shortest path length and an example.
Part (c) — 3 marks
• 1 mark — attempts to construct a 6-vertex cycle (Hamiltonian style).
• 1 mark — produces a valid cycle using only existing edges, OR rigorous justification of impossibility.
• 1 mark — clear conclusion sentence stating the cycle (or impossibility) explicitly.
Your response:
Stuck on (c)? Try S₁–S₂–S₄–S₆–S₅–S₃–S₁ — check every edge in your sequence is present.How did this worksheet feel?
What I'll revisit before next class:
1.1 — Classify A–B–C–B–D–E (2 marks)
Sample response.
Edges used: AB, BC, CB (= BC), BD, DE. Edge BC appears twice (B→C then C→B). Since an edge repeats, this is a walk only (not a trail, not a path).
Marking notes. 1 mark — correctly identifies edge BC repeats. 1 mark — states "walk only" with reasoning. A bare "walk" without justification scores 1/2.
1.2 — All paths from A to E (3 marks)
Sample response.
(a) Edges available: AB, AC, BC, BD, CD, CE, DE. Paths A → E:
— A–C–E
— A–B–C–E
— A–C–D–E
— A–B–D–E
— A–B–C–D–E
— A–B–D–C–E
— A–C–B–D–E
7 paths.
(b) Shortest length = 2 edges, e.g. A–C–E.
Marking notes. 1 mark — at least 5 paths listed. 1 mark — full enumeration with no duplicates and no invalid edges. 1 mark — shortest path correctly identified by length (2 edges) and example. Common slip: including A–E (no direct edge) or missing A–B–D–C–E.
1.3 — Garden zone network (4 marks)
Sample response.
(a) Yes — triangles include G₁–G₂–G₃–G₁ (all 3 edges present) and G₄–G₅–G₆–G₄.
(b) Connected (every garden reachable from G₁). Length-3 path G₁ → G₆ example: G₁–G₂–G₄–G₆ (uses G₁G₂, G₂G₄, G₄G₆).
(c) Edges used in G₁–G₃–G₂–G₄–G₅–G₆: G₁G₃, G₃G₂, G₂G₄, G₄G₅, G₅G₆. All five edges exist and no vertex repeats ⇒ yes, it is a path; it visits all 6 zones exactly once.
Marking notes. (a) 1 mark — names a triangle. (b) 1 mark — connectedness; 1 mark — length-3 path correct. (c) 1 mark — verifies all edges exist and concludes "path".
2.1 — Cessnock shuttle (7 marks): sample Band-6 response
Sample Band-6 response.
(a) Connected and edge count.
9 edges (S₁S₂, S₁S₃, S₂S₃, S₂S₄, S₃S₄, S₃S₅, S₄S₅, S₄S₆, S₅S₆). The network is connected — every stop is reachable from S₁ (S₂ and S₃ directly; S₄ via S₂; S₅ via S₃; S₆ via S₄ or S₅). [1 mark — 9 edges; 1 mark — connected with justification.]
(b) All paths S₁ to S₆.
Branching from S₁:
— S₁–S₂–S₄–S₆
— S₁–S₂–S₄–S₅–S₆
— S₁–S₂–S₃–S₄–S₆
— S₁–S₂–S₃–S₄–S₅–S₆
— S₁–S₂–S₃–S₅–S₆
— S₁–S₂–S₃–S₅–S₄–S₆
— S₁–S₃–S₄–S₆
— S₁–S₃–S₄–S₅–S₆
— S₁–S₃–S₂–S₄–S₆
— S₁–S₃–S₂–S₄–S₅–S₆
— S₁–S₃–S₅–S₆
— S₁–S₃–S₅–S₄–S₆
12 distinct paths. [1 mark — at least 4 listed.]
Shortest length = 3 edges (e.g. S₁–S₂–S₄–S₆ or S₁–S₃–S₄–S₆ or S₁–S₃–S₅–S₆). [1 mark — shortest correctly given.]
(c) 6-stop loop (Hamiltonian-style cycle).
Try S₁–S₂–S₄–S₆–S₅–S₃–S₁. Edges used: S₁S₂ ✓, S₂S₄ ✓, S₄S₆ ✓, S₆S₅ ✓, S₅S₃ ✓, S₃S₁ ✓. All six edges exist. Every stop visited exactly once before returning to S₁. [1 mark — attempts; 1 mark — valid cycle.]
Conclusion: a 6-stop loop is possible. The shuttle route S₁ → S₂ → S₄ → S₆ → S₅ → S₃ → S₁ visits every stop exactly once and returns to start using only existing roads. [1 mark — explicit conclusion.]
Total: 7/7.
Band descriptors for marker.
Band 3: Correct edge count; lists 2-3 paths in (b); attempts (c) but cycle uses non-existent edge. ≈ 3 marks.
Band 4: Edges and connectivity stated; 4-5 paths listed; shortest path identified; (c) cycle attempted with a single invalid step. ≈ 4-5 marks.
Band 5: All numerical parts complete; valid cycle constructed in (c) but conclusion is missing or just a bare cycle without sentence. ≈ 6 marks.
Band 6: Complete, with explicit conclusion sentence naming the cycle and stating the requirement is met. 7/7.