Walks, trails, paths, Eulerian and Hamiltonian graphs: QCE General Mathematics Unit 4 Graphs and networks
“Understand walks, trails, paths, circuits, cycles, connected graphs and bridges, the conditions for Eulerian trails and circuits in semi-Eulerian and Eulerian graphs, and Hamiltonian paths and cycles in semi-Hamiltonian and Hamiltonian graphs, and solve practical problems involving them”
A walk may repeat anything, a trail repeats no edge, and a path repeats no vertex; a closed trail is a circuit and a closed path is a cycle. A connected graph with every vertex of even degree is Eulerian (Eulerian circuit); with exactly two odd vertices it is semi-Eulerian (Eulerian trail between them). Hamiltonian paths and cycles visit every vertex once; find them by trial and error, since no degree test applies.
Jump to a section
What this dot point is asking
Many network questions are about routes: can a postie walk every street once? Can a tourist visit every attraction once and get back to the hotel? The QCAA General Mathematics 2025 syllabus asks you to use precise route vocabulary (walk, trail, path, open and closed, circuit, cycle, connected graph, bridge) and then to recognise two special kinds of route:
- Eulerian routes, which use every edge exactly once. You must know the conditions for an Eulerian trail and an Eulerian circuit, and the terms semi-Eulerian graph and Eulerian graph.
- Hamiltonian routes, which visit every vertex exactly once. You must know Hamiltonian path, semi-Hamiltonian graph, Hamiltonian cycle and Hamiltonian graph, and find them by trial and error.
Then you solve practical problems with them. This is all in Topic 3 (Graphs and networks), sub-topic "Planar graphs, paths and cycles".
The answer
Walks, trails and paths
A route through a graph is described by listing the vertices in order, such as A-B-C-D. The names depend on what is allowed to repeat.
| Route | Repeated edges? | Repeated vertices? |
|---|---|---|
| Walk | allowed | allowed |
| Trail | not allowed | allowed |
| Path | not allowed | not allowed |
Each can be open (starts and finishes at different vertices) or closed (starts and finishes at the same vertex).
- A closed trail is a circuit: it returns to its start without repeating an edge.
- A closed path is a cycle: it returns to its start without repeating any edge or any vertex (apart from the start and finish being the same vertex).
Every path is a trail, and every trail is a walk, so always give the most specific name that applies.
Two more terms:
- A graph is connected if there is a route between every pair of vertices.
- A bridge is an edge whose removal would disconnect the graph. An edge that lies on a cycle is never a bridge, because the rest of the cycle still connects its ends.
Eulerian trails and circuits
An Eulerian trail is a trail that uses every edge exactly once. An Eulerian circuit is an Eulerian trail that finishes where it started. Whether they exist depends only on the degrees of the vertices (for a connected graph):
For a connected graph: if every vertex has even degree, there is an Eulerian circuit (the graph is Eulerian), and it can start at any vertex. If exactly two vertices have odd degree, there is an Eulerian trail but no circuit (the graph is semi-Eulerian), and the trail must start at one odd vertex and finish at the other. If more than two vertices have odd degree, there is neither.
Why do the degrees decide it? Every time a trail passes through a vertex, it uses one edge to arrive and another to leave, which is two edges. So every vertex you pass through must have its edges used in pairs: even degree. Only the start and the finish can have one unpaired edge. If they are the same vertex (a circuit), even that one pairs up, so all degrees are even. If they are different (an open trail), exactly those two vertices are odd.
The number of odd-degree vertices is always even (the sum of degrees is , which is even), so you will only ever see 0, 2, 4, ... odd vertices.
In the house-shaped graph above, D and C have degree 3 and the others have degree 2. Exactly two odd vertices means the graph is semi-Eulerian: there is an Eulerian trail, and it must go from D to C (or C to D), for example D-E-C-D-A-B-C. There is no Eulerian circuit.
Making a graph Eulerian
Practical questions often ask what change would allow a route that covers every edge and returns to the start (a street sweeper, a mail run, an inspection). Every odd vertex must become even. Adding an edge between two odd vertices fixes both at once, so a graph with odd vertices needs at least extra edges (or, in the real world, roads that are travelled twice). In the house graph, adding a second edge between D and C makes every degree even, so the graph becomes Eulerian.
Hamiltonian paths and cycles
A Hamiltonian path visits every vertex exactly once; it does not need to use every edge. A Hamiltonian cycle is a Hamiltonian path that returns to its starting vertex. A graph with a Hamiltonian cycle is a Hamiltonian graph; a graph with a Hamiltonian path but no Hamiltonian cycle is semi-Hamiltonian.
Unlike Eulerian routes, there is no simple test for Hamiltonian routes, so the syllabus expects trial and error:
- Start at a vertex (a vertex of degree 1 or 2 is a good choice, because its edges are forced).
- Move to an unvisited neighbour, trying to leave awkward vertices (low degree) until they are needed.
- If you get stuck, backtrack and try a different choice.
Useful observations: a vertex of degree 1 can only be the start or end of a Hamiltonian path, and it rules out a Hamiltonian cycle. A graph with a bridge cannot have a Hamiltonian cycle either, because a cycle would have to cross the bridge twice.
The house graph is Hamiltonian: A-B-C-E-D-A visits every vertex once and returns to A (edge CD is simply not used).
Eulerian versus Hamiltonian
| Eulerian | Hamiltonian | |
|---|---|---|
| Must include | every edge exactly once | every vertex exactly once |
| Test | degrees (0 or 2 odd vertices) | no simple test: trial and error |
| Closed version | Eulerian circuit | Hamiltonian cycle |
| Open version | Eulerian trail (semi-Eulerian graph) | Hamiltonian path (semi-Hamiltonian graph) |
| Typical context | streets to sweep, tracks to inspect, mail routes | places to visit, deliveries, tours |
The two properties are independent: a graph can be Eulerian but not Hamiltonian, Hamiltonian but not Eulerian, both, or neither.
Weighted Hamiltonian problems
When edges have weights (times, distances, costs), a practical question may ask for the shortest Hamiltonian cycle, for example a courier visiting every depot once and returning. For small graphs, list the possible cycles from the start vertex and total each one. With four vertices where every pair is joined there are only three different cycles (each travelled either way), so listing is quick.
Naming routes
In the house graph (edges AB, BC, CD, DA, DE, EC), name the routes A-B-C-D-A, D-E-C-D-A and A-B-A-D.
- A-B-C-D-A
- No repeated edges, no repeated vertices except the start and finish: a cycle (closed path).
- D-E-C-D-A
- No repeated edges, but D is visited twice mid-route: an open trail (not a path).
- A-B-A-D
- Edge AB is used twice: an open walk only.
Marker's note: give the most specific name. Calling A-B-C-D-A "a walk" is true but earns no credit.
An Eulerian trail in a park
Tracks join lookouts: AB, AC, BC, BD, CD, CE and DE. Can a ranger walk every track once and return to her start?
- Degrees
- A 2, B 3, C 4, D 3, E 2.
- Test
- Two odd vertices (B and D), so the graph is semi-Eulerian: no Eulerian circuit, but an Eulerian trail from B to D exists.
- Route
- B-A-C-B-D-C-E-D uses all seven tracks once.
Marker's note: write the degrees next to each vertex on the diagram before deciding; the decision is then one line.
A Hamiltonian cycle by trial and error
Find a Hamiltonian cycle in the park graph starting at A.
Try. A-B-D-E-C-A: A to B (edge AB), B to D (BD), D to E (DE), E to C (CE), C to A (AC). All five vertices visited once, back at A.
Conclude. The park graph is Hamiltonian. (It is not Eulerian, which shows the two ideas are independent.)
Marker's note: list the edges used as well as the vertices, so the marker can see every step is a real edge.
The quickest delivery cycle
A courier starts at P and visits Q, R and S once each before returning. Times: PQ 12, PR 15, PS 10, QR 8, QS 14, RS 11 (minutes).
List the cycles. P-Q-R-S-P: 41. P-Q-S-R-P: 52. P-R-Q-S-P: 47.
Choose. P-Q-R-S-P, 41 minutes.
Marker's note: say explicitly that each cycle has the same time in reverse, so three cycles cover every possibility.
- Mixing up Eulerian and Hamiltonian
- Eulerian means every edge; Hamiltonian means every vertex. A memory aid: "Euler" and "edge" both start with E.
- Using the degree test for Hamiltonian routes
- Degrees decide Eulerian routes only. Hamiltonian routes need trial and error.
- Starting an Eulerian trail at the wrong vertex
- In a semi-Eulerian graph the trail must start and end at the two odd vertices.
- Calling a trail a path
- A path cannot revisit any vertex; a trail can.
- Forgetting to check connectivity
- The degree conditions only apply to connected graphs.
- Claiming a graph with a bridge is Hamiltonian
- A Hamiltonian cycle cannot cross a bridge (it would have to come back across it).
For any "can you travel every road / visit every town" question, first decide whether it is about edges (Eulerian) or vertices (Hamiltonian) and write that down. For Eulerian questions, write the degree of every vertex and count the odd ones. For Hamiltonian questions, show a full route listing every vertex in order. In route-naming questions, check the three things in order: repeated edges? repeated vertices? same start and finish?
Some route puzzles are about lines, and some are about dots. If you want to walk along every street exactly once, count how many streets meet at each corner: if every corner has an even number, you can do it and end where you started; if exactly two corners are odd, you can do it but must start at one odd corner and finish at the other. If you instead want to visit every place exactly once, there is no shortcut rule, so you just try routes until one works.
Practice questions
Original practice questions graded from foundation to exam level, each with a full worked solution. Try them before revealing the solution.
foundation3 marksIn a graph with vertices A, B, C, D and E, the edges are AB, BC, CD, DA, DE and EC. Classify each route as a walk, trail, path, circuit or cycle, giving the most specific name, and say whether it is open or closed. (a) A-B-C-D-A (b) D-E-C-D-A (c) A-B-A-D
Show worked solution →
(a) Starts and ends at A, no repeated edges, and no repeated vertices other than the start and end: a cycle (closed path). (1 mark)
(b) Edges DE, EC, CD, DA are all different, but vertex D appears twice (not at both ends only), so it is not a path. It starts at D and ends at A, so it is an open trail. (1 mark)
(c) Uses edge AB twice (A to B, then B back to A), so it is only a walk (an open walk, since it starts at A and ends at D). (1 mark)
foundation2 marksA connected graph has vertex degrees 2, 4, 4, 2, 6 and 2. (a) Is it Eulerian, semi-Eulerian or neither? (b) What kind of route does this guarantee?
Show worked solution →
(a) Every vertex has even degree, and the graph is connected, so it is Eulerian. (1 mark)
(b) It has an Eulerian circuit: a closed trail that uses every edge exactly once and returns to its start, which can be any vertex. (1 mark)
foundation2 marksA connected graph has vertex degrees 3, 2, 4, 3 and 2. (a) Classify the graph. (b) Where must an Eulerian trail start and finish?
Show worked solution →
(a) Exactly two vertices have odd degree (the two of degree 3), so the graph is semi-Eulerian: it has an Eulerian trail but no Eulerian circuit. (1 mark)
(b) The trail must start at one of the two odd-degree vertices and finish at the other. (1 mark)
core2 marksA connected graph has edges PQ, QR, RP, RS and ST. Identify every bridge and explain.
Show worked solution →
A bridge is an edge whose removal disconnects the graph. PQ, QR and RP form a cycle, so removing any one of them leaves the others connecting P, Q and R: none of them is a bridge. (1 mark)
Removing RS separates {S, T} from {P, Q, R}, and removing ST isolates T. So RS and ST are the bridges. (1 mark)
core3 marksA park has five lookouts A, B, C, D and E joined by tracks AB, AC, BC, BD, CD, CE and DE. (a) Find the degree of each lookout. (b) A ranger wants to walk every track exactly once, finishing where she started. Is this possible? (c) If not, where could she start and finish to walk every track exactly once, and give such a route.
Show worked solution →
(a) A 2, B 3, C 4, D 3, E 2. (1 mark)
(b) No. An Eulerian circuit needs every vertex to have even degree, but B and D are odd. (1 mark)
(c) There are exactly two odd vertices, so an Eulerian trail exists from B to D (or D to B). For example B-A-C-B-D-C-E-D uses BA, AC, CB, BD, DC, CE and ED, all seven tracks exactly once. (1 mark)
core2 marksFor the park in the previous question, find a Hamiltonian cycle starting at A, and state whether the graph is Hamiltonian.
Show worked solution →
A-B-D-E-C-A uses edges AB, BD, DE, EC and CA, visits every vertex exactly once and returns to A. (1 mark)
So the graph is Hamiltonian. (1 mark) Note that it is Hamiltonian but not Eulerian: the two properties are independent.
exam3 marksA courier must visit four depots P, Q, R and S, starting and finishing at P and visiting each other depot exactly once. Travel times in minutes are PQ 12, PR 15, PS 10, QR 8, QS 14 and RS 11. (a) What type of route is required? (b) By listing all the possibilities, find the quickest route and its time.
Show worked solution →
(a) A Hamiltonian cycle starting and finishing at P. (1 mark)
(b) With four vertices there are three distinct cycles from P (each can be travelled in either direction, with the same time):
- P-Q-R-S-P:
- P-Q-S-R-P:
- P-R-Q-S-P:
(1 mark) The quickest route is P-Q-R-S-P (or its reverse P-S-R-Q-P), taking 41 minutes. (1 mark)
exam3 marksA council inspects every road in a small network and returns to the depot. The road network is connected, and the degrees of the intersections are 2, 3, 4, 3, 3, 2 and 3. (a) Explain why an inspection route that uses every road exactly once and returns to the start is impossible. (b) What is the smallest number of new roads (edges) that would have to be added, between existing intersections, to make it possible? (c) Explain.
Show worked solution →
(a) An Eulerian circuit requires every vertex to have even degree, but there are four odd-degree intersections (the four of degree 3). (1 mark)
(b) Two new roads. (1 mark)
(c) Adding an edge between two odd vertices makes both of them even. Pairing the four odd vertices into two pairs and joining each pair with a new road makes every degree even, so an Eulerian circuit exists. One new road can fix only two odd vertices, so at least two are needed. (1 mark)