§-Syllabus dot point

WAMathematics ApplicationsSyllabus dot point

What are the different kinds of route through a graph, and when do special ones exist?

Distinguish walks, trails, paths, cycles and circuits, and determine when Eulerian and Hamiltonian routes exist.

How to tell walks, trails, paths, cycles and circuits apart, apply the odd-vertex condition for Eulerian trails and circuits, and recognise Hamiltonian paths and cycles.

Generated by Claude Opus 4.88 min answerUpdated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The route vocabulary
Eulerian routes (every edge once)
Hamiltonian routes (every vertex once)
Applying the routes

What this dot point is asking

You must distinguish the route types and apply the odd-vertex conditions for Eulerian routes, plus recognise Hamiltonian routes.

The route vocabulary

The terms build on each other by what may not be repeated.

The key distinction is edges versus vertices: trails and circuits are about not repeating edges; paths and cycles are about not repeating vertices.

Eulerian routes (every edge once)

An Eulerian route uses every edge of the graph exactly once. Whether one exists depends entirely on the number of odd-degree vertices.

This is the mathematics behind the "trace this figure without lifting your pen" puzzles and behind efficient street-sweeping or postal routes.

Hamiltonian routes (every vertex once)

A Hamiltonian route visits every vertex exactly once. A Hamiltonian path does this with different start and end; a Hamiltonian cycle returns to the start. Unlike Euler's tidy degree test, there is no simple necessary-and-sufficient condition for a Hamiltonian route in this course; you find one by inspection or systematic trial.

Worked example

Deciding which routes exist

A connected graph models five towns with these degrees: $A=2$ , $B=2$ , $C=4$ , $D=3$ , $E=3$ .

Count odd-degree vertices

Odd-degree vertices are $D$ and $E$ (both degree $3$ ): exactly two odd vertices.

Apply Euler's conditions

With exactly two odd vertices, an Eulerian trail exists but an Eulerian circuit does not. The trail must start at one odd vertex ( $D$ or $E$ ) and finish at the other.

Interpret for a road-sweeper

A sweeper can clean every road exactly once by starting at $D$ and ending at $E$ (or vice versa), with no road swept twice, which is the most efficient single run.

Hamiltonian check

Whether a Hamiltonian cycle exists (visiting each town once and returning) is found by trial. If the connections allow a closed loop through all five towns without repeating any, a Hamiltonian cycle exists; the degree counts alone do not decide it.

Applying the routes

Match the route type to the real problem: travelling every road or pipe once is Eulerian (street cleaning, mail delivery, inspecting every link); visiting every site once is Hamiltonian (a delivery tour stopping at each location, a salesperson's round). Naming the right route type and justifying it with the odd-vertex count is the examinable skill.

Exam-style practice questions

Practice questions written in the style of SCSA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

WACE 20225 marksA connected graph has vertices with degrees

4, 4, 3, 3, 2

. (a) Determine whether an Eulerian trail exists, an Eulerian circuit exists, or neither, justifying your answer. (b) Explain the practical meaning of an Eulerian trail for a postal delivery.

Show worked answer →

Count the odd-degree vertices and apply the Euler conditions.

(a) Odd-degree vertices: the two of degree $3$ , so exactly two odd vertices. An Eulerian trail (not a circuit) exists, starting at one odd vertex and ending at the other. No Eulerian circuit exists because that needs zero odd vertices. (3 marks)

(b) An Eulerian trail lets a postal worker travel every street (edge) exactly once without repeating any, which minimises wasted travel; it starts and ends at different points. (2 marks)

Markers reward counting exactly two odd vertices, concluding trail-not-circuit, and the every-edge-once interpretation.

WACE 20244 marksDistinguish between an Eulerian circuit and a Hamiltonian cycle, and state the condition for an Eulerian circuit to exist in a connected graph.

Show worked answer →

One is about edges, the other about vertices.

An Eulerian circuit travels every edge exactly once and returns to the start. A Hamiltonian cycle visits every vertex exactly once and returns to the start, but need not use every edge. (2 marks)

A connected graph has an Eulerian circuit if and only if every vertex has even degree (zero odd-degree vertices). (2 marks)

Markers reward the edges-versus-vertices distinction and the even-degree condition.