What is the difference between Eulerian and Hamiltonian travel, and how do vertex degrees decide whether an Eulerian trail or circuit exists?
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
A focused answer to the VCE General Mathematics Unit 4 Networks key-knowledge point on traversing graphs. Walks, trails, paths and cycles, the odd-degree-vertex test for Eulerian trails and circuits, and the contrast with Hamiltonian paths and cycles that visit vertices.
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
VCAA wants you to describe ways of travelling through a graph and to apply the rules for Eulerian travel. You distinguish walks, trails, paths and cycles, recognise Eulerian trails and circuits (which use every edge once) and Hamiltonian paths and cycles (which visit every vertex once), and use the count of odd-degree vertices to decide whether an Eulerian trail or circuit exists. This is the traversal half of the Networks module, separate from optimisation.
The traversal vocabulary
- A walk is any sequence of edges, with repeats allowed.
- A trail is a walk that repeats no edge.
- A path is a walk that repeats no vertex (and so no edge).
- A cycle (or circuit) is a closed path that starts and ends at the same vertex.
These distinctions matter because the Eulerian and Hamiltonian conditions are stated in terms of them.
The odd-degree test for Eulerian travel
The degree of a vertex is the number of edges meeting it. The existence of Eulerian travel in a connected graph depends only on how many vertices have odd degree:
- Zero odd-degree vertices: an Eulerian circuit exists (and so does a trail). You can start anywhere and return to it.
- Exactly two odd-degree vertices: an Eulerian trail exists but not a circuit. You must start at one odd vertex and finish at the other.
- More than two odd-degree vertices: no Eulerian trail or circuit exists.
Hamiltonian paths and cycles
A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle does the same and returns to the start. Unlike the Eulerian case, there is no simple degree test, so in VCE you find one by inspection, listing a sequence of vertices that visits each once. The everyday example is a delivery van that must call at every house (vertex) once, regardless of which roads it uses.
Why this matters for the exams
Eulerian questions are quick marks once you can count odd-degree vertices and state which kind of travel is possible and where it must start and end. Markers reward the correct count, the right conclusion, and naming the start and finish vertices for a trail. The Hamiltonian contrast is tested by asking you to write out a valid sequence of vertices, reinforcing the edge-versus-vertex distinction.
Exam-style practice questions
Practice questions written in the style of VCAA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
2025 VCAA1 marksOn a graph, the vertices represent Frances's favourite locations and the edges represent the roads between them. 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 key feature is that the route visits each vertex (location) exactly once, starting at one vertex (the gym) and finishing at a different vertex (home).
A route that visits every vertex exactly once is a Hamiltonian route. Because it starts and ends at different vertices (it does not return to the start), it is a Hamiltonian path, not a Hamiltonian cycle.
The mark is awarded for the term Hamiltonian path. (A Hamiltonian cycle would be required only if she had to return to the gym.)
2025 VCAA1 marksOn a network the vertices are stations and the edges are walkways. The gym owner wants to inspect every walkway, beginning and ending the inspection at station A. Explain, with reference to the degrees of the vertices, why the gym owner's intended route must involve some repeated edges.Show worked answer →
Travelling along every edge and returning to the start is an Eulerian circuit. An Eulerian circuit exists only when the graph is connected and every vertex has an even degree, because each time you enter a vertex along one edge you must leave it along a different edge.
In this network at least one vertex (in fact more than zero) has an odd degree. At an odd-degree vertex the edges cannot be paired up into enter-and-leave pairs, so the route cannot use every edge exactly once and still close up at A.
Therefore some edges must be travelled more than once. The mark requires linking the need for repeated edges to the presence of odd-degree vertices.