Walks, paths, Eulerian and Hamiltonian routes in WACE Mathematics Applications Unit 3

Syllabus dot point

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

WACEMathematics ApplicationsUnit 38 min readUpdated 2 Jun 2026

Quick answer

A walk is any route along edges; a trail repeats no edge; a path repeats no vertex. A circuit is a closed trail and a cycle is a closed path. An Eulerian trail uses every edge once (it exists when exactly two vertices have odd degree); an Eulerian circuit uses every edge once and returns to start (it exists when every vertex has even degree). A Hamiltonian path visits every vertex once, and a Hamiltonian cycle returns to start.

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
Exam-style questions

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.

Route types

A walk is any sequence of connected edges (repeats allowed). A trail is a walk with no repeated edge. A path is a walk with no repeated vertex (and so no repeated edge). A circuit (closed trail) starts and ends at the same vertex with no repeated edge. A cycle (closed path) starts and ends at the same vertex with no repeated vertex in between.

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.

Euler's conditions (connected graph)

Eulerian circuit (every edge once, returns to start): exists if and only if every vertex has even degree (zero odd vertices).
Eulerian trail (every edge once, different start and end): exists if and only if exactly two vertices have odd degree; the trail starts at one and ends at the other.
If there are more than two odd-degree vertices, no Eulerian route exists.

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.

Euler counts edges, Hamilton counts vertices

Eulerian routes traverse every edge once; Hamiltonian routes visit every vertex once. A graph can have one without the other. The odd-vertex test only applies to Eulerian routes.

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.

Common errors

Confusing Eulerian and Hamiltonian: Eulerian is every edge once; Hamiltonian is every vertex once. Read whether the task is about traversing links or visiting locations.
Miscounting odd-degree vertices: Recount degrees carefully; the number of odd vertices ( $0$ , $2$ , or more) decides everything for Euler.
Expecting a degree rule for Hamilton: There is no simple degree condition for Hamiltonian routes; find them by inspection.
Mixing trail and path: Trails do not repeat edges; paths do not repeat vertices. A circuit is a closed trail; a cycle is a closed path.

Exam-style questions

Questions in the style of SCSA exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.

WACE 2022-style5 marks

A 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 2024-style4 marks

Distinguish 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.