Mathematics Standard • Year 12 • Module 5 • Lesson 3
Paths, Trails and Cycles — Skill Drill
Build fluency in identifying and constructing walks, trails, paths, circuits and cycles, and in finding all routes between two vertices.
1. Quick recall
Answer each question in the space provided. 1 mark each
Q1.1 Fill the hierarchy of routes from most flexible to most restrictive:
___________________ ⊃ ___________________ ⊃ ___________________
Q1.2 A circuit is a closed __________; a cycle is a closed __________.
Q1.3 Minimum number of edges in any cycle = __________
2. Worked example — finding all paths from A to E
Problem. Network with vertices A, B, C, D, E and edges AB, AC, BC, BD, CD, CE, DE. Find every path from A to E.
Step 1 — List the direct neighbours of A.
From A we can go to B or C.
Step 2 — Branch through B without revisiting A.
A–B–C–E ✓ (path: no repeats)
A–B–C–D–E ✓
A–B–D–E ✓
A–B–D–C–E ✓
Step 3 — Branch through C without revisiting A.
A–C–E ✓
A–C–D–E ✓
A–C–B–D–E ✓
Conclusion. All paths A → E: A–C–E, A–C–D–E, A–C–B–D–E, A–B–C–E, A–B–C–D–E, A–B–D–E, A–B–D–C–E (7 paths).
3. Faded example — find all cycles in a square with one diagonal
Network: square ABCD with edges AB, BC, CD, DA and diagonal AC. Find all cycles. 4 marks
Step 1 — Count the vertices and edges. n = ____, edges = ____.
Step 2 — Triangle cycles (3 edges).
The diagonal AC splits the square into two triangles: ____–____–____–____ and ____–____–____–____ (write each as a cycle ending at the start vertex).
Step 3 — 4-vertex cycle. The full square: ____–____–____–____–____
Total cycles found: ____ (count each cycle once, ignoring direction).
4. Graduated practice — routes and connectivity
Foundation — single-step facts (4 questions)
| Q | Problem | Answer |
|---|---|---|
| 4.1 1 | State whether A–B–C–B–A is a walk, trail, or path (assuming edges AB, BC exist). | |
| 4.2 1 | State whether A–B–C–A is a cycle (assuming edges AB, BC, CA exist). | |
| 4.3 1 | How many components does a network with vertices A, B, C, D, E and edges AB, BC, DE have? | |
| 4.4 1 | True or false: every path is a trail. |
Standard — typical HSC difficulty (6 questions)
4.5 Network: triangle ABC. Find all cycles starting and ending at A. 2 marks
4.6 Network: complete graph K₄ on A, B, C, D. Find all paths from A to D. 2 marks
4.7 Network: A–B–C–D (a 3-edge path). Classify each route below as walk, trail, path or none:
(a) A–B–C–D (b) A–B–A–B–C–D (c) A–B–C–B–C–D (d) A–C (no edge AC) 2 marks
4.8 Network: pentagon ABCDE with one diagonal AC. Find all paths from B to D. 2 marks
4.9 A maze has 6 rooms and 8 doors. Connections: R₁–R₂, R₁–R₃, R₂–R₃, R₂–R₄, R₃–R₅, R₄–R₅, R₄–R₆, R₅–R₆. Is the network connected? Find the shortest path (in number of doors) from R₁ to R₆. 2 marks
4.10 A network has two components: {A, B, C} fully connected as a triangle, and {D, E} connected by an edge. Find any path from A to D. 2 marks
Extension — combine ideas (2 questions)
4.11 In the network with edges AB, BC, CD, DE, EA, AC, BD (a pentagon ABCDE plus diagonals AC and BD): (a) Find all 3-edge cycles starting and ending at A. (b) Find the longest cycle. 3 marks
4.12 In the same network as Q4.11, find all paths from A to D that use at most 3 edges. 3 marks
5. Self-check the easy 3
Tick the first three once you've checked your method works.
How did this worksheet feel?
What I'll revisit before next class:
Q1.1 — Hierarchy
Walk ⊃ Trail ⊃ Path (most flexible to most restrictive).
Q1.2 — Circuit vs cycle
Circuit = closed trail (no repeated edges). Cycle = closed path (no repeated vertices except start = end).
Q1.3 — Minimum cycle length
3 edges (a triangle).
Q3 — Faded example (square ABCD with diagonal AC)
Step 1: n = 4, edges = 5.
Step 2: Triangles A–B–C–A and A–C–D–A.
Step 3: 4-vertex cycle A–B–C–D–A.
Total cycles found: 3.
Q4.1 — A–B–C–B–A
Edges used: AB, BC, CB (= BC), BA (= AB). Edges BC and AB both repeat ⇒ walk only.
Q4.2 — A–B–C–A
Closed (start = end = A), no other repeats, edges AB, BC, CA all distinct ⇒ yes, a cycle.
Q4.3 — Components
{A, B, C} (joined by AB, BC) and {D, E} (joined by DE) ⇒ 2 components.
Q4.4 — Every path is a trail?
True. A path has no repeated vertices, so it cannot have repeated edges, so it is automatically a trail.
Q4.5 — Cycles in triangle ABC starting and ending at A
Only one (counted once regardless of direction): A–B–C–A. (Reverse A–C–B–A is the same cycle traversed backwards.)
Q4.6 — All paths from A to D in K₄
K₄ has edges AB, AC, AD, BC, BD, CD. Paths from A to D:
— A–D
— A–B–D
— A–C–D
— A–B–C–D
— A–C–B–D
5 paths.
Q4.7 — Classify in path A–B–C–D
(a) A–B–C–D: path. (b) A–B–A–B–C–D: edge AB repeated ⇒ walk only. (c) A–B–C–B–C–D: edge BC repeated ⇒ walk only. (d) A–C: none (edge AC does not exist).
Q4.8 — Paths from B to D in pentagon ABCDE + diagonal AC
Edges available: AB, BC, CD, DE, EA, AC. From B:
— B–C–D
— B–A–C–D
— B–A–E–D
— B–C–A–E–D
4 paths.
Q4.9 — Maze connectivity and shortest R₁ → R₆
Yes, connected. Shortest path: R₁–R₃–R₅–R₆ or R₁–R₂–R₄–R₆ — both are 3 doors long.
Q4.10 — Path from A to D across two components
No path exists — A is in {A, B, C} and D is in {D, E}; there is no edge between the two components. (Disconnected networks have no path between vertices in different components.)
Q4.11 — Pentagon ABCDE + diagonals AC, BD
Edges: AB, BC, CD, DE, EA, AC, BD.
(a) 3-edge cycles at A: A–B–C–A (uses AB, BC, CA). Any others? A–B–D–? D needs to connect back to A — no edge DA. A–C–B–A — same triangle reversed. So just one 3-edge cycle at A: A–B–C–A.
(b) Longest cycle uses all 5 vertices: A–B–C–D–E–A (5-edge cycle, the pentagon).
Q4.12 — Paths A → D using at most 3 edges (same network as 4.11)
Direct? AD does not exist. 1-edge: none. 2-edge: A–C–D (yes), A–B–D (yes via BD). 3-edge: A–B–C–D, A–C–B–D, A–E–D? — ED exists, so A–E–D is 2 edges (= A–E–D via EA reversed and ED).
Re-listing by length:
— 2 edges: A–B–D, A–C–D, A–E–D.
— 3 edges: A–B–C–D, A–C–B–D, A–E–D requires only 2 edges so already counted; A–E–D plus one more would revisit.
5 paths in total: A–B–D, A–C–D, A–E–D, A–B–C–D, A–C–B–D.