When can we trace every edge, or visit every vertex, of a network exactly once?
Identify and find Eulerian trails and circuits and Hamiltonian paths and cycles in networks.
Walks, trails, paths, Eulerian trails and circuits, Hamiltonian paths and cycles, and the vertex-degree conditions that decide them in TCE Mathematics Applications.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
What this dot point is asking
Two famous network problems ask very different things. One is about covering every edge, the other about covering every vertex. Telling them apart, and knowing the test for each, is the heart of this dot point.
Eulerian trails and circuits
An Eulerian trail uses every edge of the network exactly once. If it also starts and finishes at the same vertex, it is an Eulerian circuit. The test depends entirely on counting odd-degree vertices.
This is the mathematics behind a postal or street-sweeping route, where every road (edge) must be covered once. If more than two vertices are odd, no single trail can cover all edges without repeating one.
Hamiltonian paths and cycles
A Hamiltonian path visits every vertex exactly once. If it returns to its starting vertex, it is a Hamiltonian cycle. This models a delivery run that must call at every town (vertex) once, regardless of which roads are used.
No edge or vertex repeats
Remember that an Eulerian trail may repeat vertices but never edges, while a Hamiltonian path may skip edges but never repeats a vertex. These are opposite restrictions, which is why a route can be one without being the other.
Why the degree test works
Every time an Eulerian trail passes through a vertex, it uses one edge to arrive and one edge to leave, accounting for edges in pairs. So any vertex that is neither the start nor the finish must have an even degree. In a closed trail (circuit) the start and finish coincide, so that vertex is also entered and left in pairs, forcing every vertex to be even. In an open trail the two endpoints are the only vertices that can be odd, which is exactly why an Eulerian trail needs precisely zero or two odd vertices. Counting odd-degree vertices therefore settles the question completely: zero gives a circuit, two gives an open trail, and four or more means no single trail can cover every edge.
A complete answer names whether the task is Eulerian (edges) or Hamiltonian (vertices), applies the odd-degree count for Eulerian cases (zero odd for a circuit, two odd for an open trail), and for Hamiltonian cases states a specific route that visits every vertex once, noting whether it is a path or a cycle.
Exam-style practice questions
Practice questions written in the style of TASC exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
TCE 20245 marksFigure 8 represents footpaths at a wildlife sanctuary, with distances in metres. a) Find a trail starting at A (the mammals) that uses all of the footpaths once and returns to A. Write your answer as a sequence of letters. b) What is the term given to this kind of trail? c) How can you tell that such a trail is possible, before actually finding it? d) Find the length of the shortest closed Hamiltonian Path, starting and finishing at C (the reptiles).Show worked answer →
a) (2 marks) Trace a route that travels every edge exactly once and ends back at A, writing the vertices in order (for example A B D G E C A, depending on the diagram). Each footpath must be used once and only once.
b) (1 mark) It is an Eulerian circuit (Eulerian trail that starts and finishes at the same vertex).
c) (1 mark) An Eulerian circuit exists if and only if the network is connected and every vertex has an even degree (an even number of edges meeting at it). Checking that there are no odd-degree vertices confirms a circuit is possible before finding it.
d) (1 mark) A Hamiltonian path visits every vertex exactly once. Find the closed route from C through all vertices and back to C with the smallest total of the edge distances, and report that minimum length in metres.
TCE 20192 marksA garden network is shown. a) A mathematician wishes to make a Hamiltonian circuit around the garden. What do they mean? b) What would be meant by an Eulerian circuit of the garden, and is one possible? How can you tell?Show worked answer →
a) (1 mark) A Hamiltonian circuit is a closed route that visits every vertex (location in the garden) exactly once and returns to the start. It need not use every edge.
b) (1 mark) An Eulerian circuit is a closed route that travels along every edge (path) exactly once and returns to the start. It is possible only if the network is connected and every vertex has even degree. Count the edges at each vertex: if any vertex has odd degree, no Eulerian circuit exists; if all are even, one exists.