Euler and Hamilton paths and circuits: VCE General Mathematics Unit 4 Networks and decision mathematics

Syllabus dot point

“Distinguish walks, trails, paths, cycles, Eulerian trails and circuits, and Hamiltonian paths and cycles, and use the number of odd-degree vertices to decide whether an Eulerian trail or circuit exists in a connected graph”

15 min readUpdated 23 Sep 2026

Quick answer

Eulerian means every edge once; Hamiltonian means every vertex once. A connected graph has an Eulerian circuit when every vertex has even degree, and an Eulerian trail (not a circuit) when exactly two vertices have odd degree; the trail starts at one odd vertex and ends at the other. If there are odd vertices and every edge must be covered, repeat the shortest paths joining them. There is no degree test for Hamiltonian routes: find them by inspection, using the fact that both edges at a degree-2 vertex must be used.

Jump to a section

What this dot point is asking
The answer
Travelling problems in context
Exam-style questions
Practice questions

What this dot point is asking

Under "Exploring and travelling problems" the Study Design lists:

"the concepts, conventions and notations of walks, trails, paths, cycles and circuits";
"Eulerian trails and Eulerian circuits: the conditions for a graph to have a Eulerian trail or a Eulerian circuit, properties and applications";
"Hamiltonian paths and cycles: properties and applications".

So you need the vocabulary, the degree test for Eulerian travel, and the ability to find or count Hamiltonian routes in a small graph. Recent papers tested all three: naming a route (2025 Examination 2 Question 15c, $53\%$ ), explaining why edges must be repeated and finding the shortest inspection route (2025 Examination 2 Question 17, $40\%$ and $27\%$ ), counting Hamiltonian cycles (2025 Examination 1 Question 33, $76\%$ ), and a Hamiltonian cycle plus a repeated-roads trail on a nine-vertex map (2023 Examination 2 Question 13b and c, $44\%$ and only $12\%$ ).

The answer

The vocabulary

A walk is any sequence of edges joining one vertex to the next. The other names add restrictions:

Name	Repeated edges?	Repeated vertices?	Starts and ends at the same vertex?
walk	allowed	allowed	either
trail	no	allowed	no (open)
path	no	no	no (open)
circuit	no	allowed	yes (closed)
cycle	no	no (except start = finish)	yes (closed)

Every path is a trail, and every cycle is a circuit, but not the other way round. When asked for "the mathematical term", give the most specific name.

Eulerian trails and circuits

An Eulerian trail uses every edge exactly once. An Eulerian circuit is an Eulerian trail that starts and finishes at the same vertex. (Both are named after Euler, whose Königsberg bridges problem started graph theory.)

Each time a route passes through a vertex it uses two edges, one in and one out. So:

if the route is closed, every vertex has its edges paired, and every degree is even;
if the route is open, the start and finish each have one unpaired edge, so exactly those two vertices have odd degree.

For a connected graph this gives the test:

Number of odd-degree vertices	Eulerian circuit?	Eulerian trail?
0	yes (start anywhere)	yes (it is a circuit)
2	no	yes, from one odd vertex to the other
4, 6, ...	no	no

The number of odd vertices is always even, because the sum of the degrees is twice the number of edges (the handshaking result: $\text{sum of degrees} = 2e$ ).

Formula

Sum of degrees $= 2 \times$ number of edges. Connected graph: all degrees even $\Rightarrow$ Eulerian circuit; exactly two odd $\Rightarrow$ Eulerian trail between them; more than two odd $\Rightarrow$ neither.

When edges must be repeated

Inspection, cleaning, mail and snowplough problems need every edge covered. If the graph has odd vertices, some edges must be walked twice, and each repeated edge adds 1 to the degree of both of its ends. To finish with an Eulerian route:

closed route (back to the start): pair up all the odd vertices and repeat the shortest path between each pair;
open route from a given start: the start and the finish may stay odd; pair up the others.

With two odd vertices and a closed route, the minimum distance is the total of all edges plus the shortest path between the two odd vertices. The figure shows 2025 Examination 2 Question 17.

Hamiltonian paths and cycles

A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle does so and returns to the start. There is no simple degree test. Find them by inspection:

any vertex of degree 2 has both its edges in every Hamiltonian cycle;
a vertex of degree 1 can only be an end of a Hamiltonian path, so a graph with a degree-1 vertex has no Hamiltonian cycle;
once a vertex has two chosen edges, its other edges cannot be used.

For the shortest Hamiltonian cycle in a small weighted graph (a travelling problem such as visiting every landmark and returning), list the possible cycles and add their lengths. When counting cycles "starting from" a vertex, a cycle and its reverse are usually counted separately (2025 Examination 1 Question 33 had one cycle, travelled in two directions: answer 2).

Eulerian and Hamiltonian properties are independent: a graph can have either, both or neither.

Worked examples: Eulerian tests, repeated edges and Hamiltonian routes

Why edges must be repeated (2025 Examination 2 Question 17a)

Step 1: degrees: A 6 (B, C, D, E, F, H), B 2, C 3 (A, B, D), D 2, E 1, F 2, G 2, H 2.
Step 2: link to the condition: Walking every walkway once and returning to A is an Eulerian circuit, which needs every vertex even. C and E are odd.
Answer: "Vertices C and E have odd degree. An Eulerian circuit requires all vertices to have even degree, so some edges must be repeated." Only $40\%$ wrote a complete answer; naming the odd vertices is what earns the mark.

The minimum inspection distance (2025 Examination 2 Question 17b)

Step 1: add every edge: $8 + 14 + 12 + 22 + 19 + 28 + 11 + 23 + 31 + 7 = 175$ m.
Step 2: shortest path between the odd vertices: C to E: via A is $14 + 7 = 21$ ; via B and A is $12 + 8 + 7 = 27$ ; via D and A is $22 + 19 + 7 = 48$ . Use C-A-E.
Step 3: add: $175 + 21 = 196$ m. Repeating C-A and A-E raises C to degree 4, E to 2 and A to 8, so every vertex is now even and a circuit from A exists, for example A-E-A-C-A-B-C-D-A-H-G-F-A (with A-C and A-E each walked twice).

Which roads to repeat for an open route (2023 Examination 2 Question 13c)

Step 1: find the odd vertices: G, H, J, L, M and N have degree 3; I, K and O have degree 4.
Step 2: decide which may stay odd: Shyla starts at G and ends somewhere else, so G and one other vertex stay odd. The other four must be paired by repeated roads.
Step 3: pair them with single roads: Among H, J, L, M, N, the odd pairs joined by a road are J-M (2.1) and L-N (1.8). H's only odd neighbour is G, which must stay odd. So repeat J-M and L-N; the trail runs from G to H.
Step 4: total: All roads add to 31.5 km, so Shyla's journey is $31.5 + 2.1 + 1.8 = 35.4$ km. Only $12\%$ found both pairs.

A shortest Hamiltonian cycle (2023 Examination 2 Question 13b)

Step 1: start with the awkward vertices. J (joined to I, M, O) and M (joined to I, J, O) are on the far side of the map, so a short cycle should pass through them together using the short edge J-M (2.1).

Step 2: build and compare. G-H-K-I-J-M-O-L-N-G: $1.7 + 1.1 + 1.2 + 2.8 + 2.1 + 2.6 + 1.4 + 1.8 + 1.8 = 16.5$ km. Checking every Hamiltonian cycle from G (there are 12, counting each direction) confirms 16.5 km is the minimum, achieved by this cycle and its reverse.

Marker's note: the report accepted either direction. Many students missed a landmark in the middle or did not return to G.

Naming a route (2025 Examination 2 Question 15c)

The route starts at the gym, visits each other location once and ends at home. Every vertex once, different start and end: a Hamiltonian path. It is not a cycle (it does not return to the gym) and not Eulerian (it does not use every road).

Common traps

Mixing up Euler and Hamilton. Euler: every edge once. Hamilton: every vertex once. A quick memory aid: "Euler Edges".

Saying "all vertices are odd" or "some vertices are odd" without naming them. Explanations need the specific odd vertices and the condition they break.

Giving the wrong route type: A route that returns to its start is a cycle or circuit; one that does not is a path or trail. "Visit each location once and end at home" is a Hamiltonian path.
Adding the wrong repeat: Repeat the shortest path between odd vertices, which may be several edges long, not the shortest single edge in the graph.
Forgetting the start in an open route: If the route must start at an odd vertex and end elsewhere, that start vertex stays odd; pair up the others.
Counting a Hamiltonian cycle once when the question counts directions: "Starting from E" in 2025 Examination 1 Question 33 counted both directions.

Exam technique

Write the degree of every vertex next to it before answering any Eulerian question; it takes seconds and answers "trail, circuit or neither" immediately. For inspection problems, total all the edges first, then list the possible paths between the odd vertices with their lengths and pick the shortest. For Hamiltonian questions, mark the edges forced by degree-2 vertices first; they usually leave only one or two possible cycles.

Travelling problems in context

Eulerian problems are about covering connections: every road, pipe, walkway or cable (road inspections, rubbish collection, cleaning routes). Hamiltonian problems are about visiting places: every town, landmark or station (delivery rounds, tourist routes, the travelling salesperson). Deciding which one a question describes is the first mark in many short-answer items, and the choice of shortest-path, spanning-tree or Hamiltonian-cycle method follows from it.

Note

Some route problems ask you to use every road once (Eulerian) and some ask you to visit every place once (Hamiltonian). For roads, count how many roads meet at each place. If every place has an even number, you can use every road once and come back to where you started. If exactly two places have an odd number, you can use every road once but must start at one of them and finish at the other. Otherwise some roads have to be used twice, and you should repeat the shortest ones that link the odd places. For visiting places there is no counting rule; you try routes, starting with places that have only two roads, because both of those roads must be used.

Exam-style questions

Questions in the style of VCAA 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.

2025 VCAA Exam 2 Q15cPast paper1 mark

Frances lives in a housing estate. On the graph the vertices represent her favourite locations, and the edges represent the roads between them. [Graph: edges gym - coffee shop, gym - pet shop, coffee shop - supermarket, coffee shop - pet shop, coffee shop - home, supermarket - home, pet shop - home.] Frances is at the gym. She would like to visit each of the other locations once and end at her home. What is the mathematical term used to describe this route?

Show worked answer →

The route visits every vertex exactly once and starts and finishes at different vertices. That is a Hamiltonian path. (One exists: gym, pet shop, coffee shop, supermarket, home.)

Only $53\%$ scored the mark. The common wrong answers were "Hamiltonian cycle" (a cycle returns to the start) and "Eulerian trail" (Eulerian routes are about using every edge once, not visiting every vertex).

Source: VCAA 2025 General Mathematics Examination 2, Question 15c, and the 2025 examination report.

2025 VCAA Exam 2 Q17Past paper2 marks

The gym is hosting a competition at eight different stations. On the network, the vertices represent the stations. The edges represent the walkways between the stations and the numbers show the distance, in metres, between them. [Network: A - B 8, A - C 14, B - C 12, C - D 22, A - D 19, A - H 28, H - G 11, G - F 23, F - A 31, A - E 7.] The gym owner would like to make sure that all the walkways are clear before the competition starts. The gym owner would like to begin and end the inspection of the walkways at station A. a. Explain, with reference to the degrees of the vertices, why the gym owner's intended route must involve some repeated edges. b. What is the minimum distance, in metres, that the gym owner will cover when completing the inspection?

Show worked answer →

(a) Walking every edge exactly once and returning to $A$ would be an Eulerian circuit, which needs every vertex to have even degree. Here $C$ (degree 3) and $E$ (degree 1) have odd degree, so no Eulerian circuit exists and some edges must be repeated. (1 mark; $40\%$ . Naming the odd vertices and linking them to the Eulerian circuit condition was needed.)

(b) Sum of all edges $= 8 + 14 + 12 + 22 + 19 + 28 + 11 + 23 + 31 + 7 = 175$ m. Repeat the shortest path joining the two odd vertices: $C$ to $A$ to $E$ , $14 + 7 = 21$ m (C to B to A to E is 27, C to D to A to E is 48). Minimum distance $= 175 + 21 =$ 196 m. (1 mark; $27\%$ .)

Source: VCAA 2025 General Mathematics Examination 2, Question 17, and the 2025 examination report.

2025 VCAA Exam 1 Q33Past paper1 mark

Consider the following graph. [Graph with vertices

A

F

and edges

AB

BC

CD

DE

BE

EF

and

FA

.] The number of Hamiltonian cycles in this graph, starting from

E

, is A. 0 B. 2 C. 4 D. 6

Show worked answer →

A and F have degree 2, so both of their edges must be in any Hamiltonian cycle: $F$ - $E$ , $F$ - $A$ and $A$ - $B$ are forced. C and D also have degree 2, so $B$ - $C$ , $C$ - $D$ and $D$ - $E$ are forced. Those six edges form the cycle $E, F, A, B, C, D, E$ , and edge $BE$ is not used.

Starting from $E$ the cycle can be travelled in two directions: $E$ - $F$ - $A$ - $B$ - $C$ - $D$ - $E$ and $E$ - $D$ - $C$ - $B$ - $A$ - $F$ - $E$ . Answer B ( $76\%$ correct).

Source: VCAA 2025 General Mathematics Examination 1, Question 33, and the 2025 examination report.

2023 VCAA Exam 2 Q13b-cPast paper2 marks

The state A has nine landmarks, G to O. The edges represent the roads between the landmarks and the numbers are lengths in kilometres. [Graph: G - H 1.7, G - K 1.5, G - N 1.8, H - K 1.1, H - I 3.2, K - I 1.2, K - L 0.9, I - M 3.2, I - J 2.8, M - J 2.1, L - N 1.8, L - O 1.4, M - O 2.6, N - O 2.4, J - O 3.8.] Three friends meet at landmark G. b. Reynold would like to visit all the landmarks and return to G. Write down a route that Reynold could follow to minimise the total distance travelled. c. Shyla would like to travel along all the roads. To complete this journey in the minimum distance, she will travel along two roads twice. Shyla will leave from landmark G but end at a different landmark. Which two roads will be travelled along twice?

Show worked answer →

(b) Visiting every landmark and returning to $G$ is a Hamiltonian cycle. The shortest is G-H-K-I-J-M-O-L-N-G (or the reverse), $1.7 + 1.1 + 1.2 + 2.8 + 2.1 + 2.6 + 1.4 + 1.8 + 1.8 = 16.5$ km. (1 mark; $44\%$ . Many missed a landmark or did not end at G.)

(c) Degrees: $G, H, J, L, M, N$ are odd (3 each); $I, K, O$ are even (4). A trail from $G$ to another vertex needs exactly two odd vertices, one of them $G$ . Repeating a road adds 1 to the degree of each end, so repeat roads that join pairs of the other odd vertices: L-N and J-M. Only $G$ and $H$ stay odd, so Shyla finishes at $H$ . (1 mark; only $12\%$ .)

Source: VCAA 2023 General Mathematics Examination 2, Question 13, and the 2023 examination report.

Practice questions

Original practice questions graded from foundation to exam level, each with a full worked solution. Try them before revealing the solution.

foundation3 marks

A graph has edges P-Q, Q-R, R-S, S-T, T-P and P-R. Classify each sequence as a walk, trail, path or cycle (give the most specific name). (a) P-Q-R-P-T (b) Q-R-S-T-P (c) P-Q-R-S-T-P (d) P-R-S-T-P-R

Show worked solution →

(a) Edges P-Q, Q-R, R-P, P-T: none repeated, but vertex P is repeated and the route is open: a trail.

(b) No repeated vertex or edge, open: a path.

(c) Closed, no repeated vertex apart from the start/finish: a cycle (it visits all five vertices, so it is also a Hamiltonian cycle).

(d) Edges P-R, R-S, S-T, T-P, P-R: the edge P-R is used twice, so it is only a walk.

(3 marks: 1 for (a) and (b), 1 for (c), 1 for (d).) Always check for repeated edges before calling something a trail or circuit.

foundation2 marks

A connected graph has vertices with degrees 4, 3, 3, 2, 2 and 2. (a) How many edges does it have? (b) Does it have an Eulerian trail, an Eulerian circuit, or neither?

Show worked solution →

(a) Sum of degrees $= 16 = 2e$ , so $e = 8$ . (1 mark)

(b) Exactly two vertices have odd degree, so it has an Eulerian trail (starting at one degree-3 vertex and ending at the other) but not an Eulerian circuit. (1 mark)

core3 marks

A park has paths P-Q 4, Q-R 6, R-S 5, S-T 3, T-P 7 and P-R 8 (lengths in hundreds of metres). (a) Explain why a ranger can walk every path exactly once, and state where the walk must start and finish. (b) Write down one such route and its length. (c) The ranger must start and finish at P. Find the shortest route length.

Show worked solution →

(a) Degrees: P 3, Q 2, R 3, S 2, T 2. The graph is connected with exactly two odd vertices, so an Eulerian trail exists, starting at P and finishing at R (or the reverse). (1 mark)

(b) P-Q-R-S-T-P-R uses each of the six paths once: $4 + 6 + 5 + 3 + 7 + 8 = 33$ , so 3300 m. (1 mark)

(c) The shortest path from R back to P is the direct path (8), shorter than R-Q-P (10). Repeat it: $33 + 8 = 41$ , so 4100 m. (1 mark)

core2 marks

For the park in the previous question, a new path Q-S of length 9 is built. (a) Does the new network have an Eulerian trail? (b) List the Hamiltonian cycles that start at P and find the shortest.

Show worked solution →

(a) Degrees become P 3, Q 3, R 3, S 3, T 2: four odd vertices, so no Eulerian trail. (1 mark)

(b) T has degree 2, so S-T and T-P are in every Hamiltonian cycle. The cycles from P are P-Q-R-S-T-P ( $4 + 6 + 5 + 3 + 7 = 25$ ), P-R-Q-S-T-P ( $8 + 6 + 9 + 3 + 7 = 33$ ) and their reverses. Shortest: P-Q-R-S-T-P, 25 (2500 m). (1 mark)

exam2 marks

A connected graph has six vertices with degrees 3, 3, 2, 4, 3 and 3 (vertices U, V, W, X, Y, Z in order). A council wants an Eulerian circuit and will add as few new edges as possible between existing vertices. (a) What is the minimum number of edges it must add? (b) Explain your answer.

Show worked solution →

(a) 2 edges. (1 mark)

(b) There are four odd vertices (U, V, Y, Z). Each new edge changes the degree of two vertices by 1, so one edge can make at most two odd vertices even. Two new edges, each joining a pair of the odd vertices (for example U to V and Y to Z), make every degree even, and an Eulerian circuit then exists. (1 mark)

exam2 marks

A graph has vertices A to F and edges AB, BC, CD, DE, BE, EF and FA (as in 2025 Examination 1 Question 33). (a) Does it have an Eulerian circuit? (b) Does it have an Eulerian trail? If so, where must it start and finish?

Show worked solution →

Degrees: A 2, B 3, C 2, D 2, E 3, F 2.

(a) No: B and E have odd degree. (1 mark)

(b) Yes: exactly two odd vertices, so an Eulerian trail runs from B to E (or E to B), for example B-A-F-E-B-C-D-E. (1 mark) Note that the same graph has a Hamiltonian cycle (E-F-A-B-C-D-E) but no Eulerian circuit: the two ideas are independent.

Practise this

Sources & how we know this

VCE General Mathematics Examination 2 (2023) and examination report — VCAA (2023)
VCE General Mathematics Examination 1 (2025) and examination report — VCAA (2025)
VCE General Mathematics Examination 2 (2025) and examination report — VCAA (2025)
VCE Mathematics Study Design: General Mathematics (from 2023) — VCAA
VCE General Mathematics: examination specifications, past examinations and reports — VCAA