Trails, circuits, Euler and Hamiltonian paths
Master trails, circuits, Euler and Hamiltonian paths in Year 11 VCE Specialist Mathematics. A trail repeats no edge and a circuit is a closed trail; an Euler trail uses every edge once, while a Hamiltonian path visits every vertex once. It sits in the Algebra, number and structure area of study of the VCE Mathematics Study Design (VCAA), within the Graph theory topic of Unit 1.
You will learn the odd-degree tests — an Euler trail needs \(0\) or \(2\) odd vertices and an Euler circuit needs none — distinguish Euler routes from Hamiltonian ones, and see why the famous Königsberg bridge problem has no solution.
Theory
A trail is a walk that never repeats an edge, and a circuit is a closed trail. In Year 11 Specialist Mathematics you use two clean tests based on vertex degree: a connected graph has an Euler trail (using every edge exactly once) precisely when \(0\) or \(2\) vertices have odd degree, and an Euler circuit precisely when every vertex has even degree. A Hamiltonian path instead visits every vertex once. These ideas grew out of the famous Königsberg bridge problem.
A walk is any sequence of edges that joins one vertex to the next. A trail is a walk with no repeated edge (a vertex may be revisited); a circuit is a closed trail — it finishes where it began.
The degree of a vertex is the number of edge-ends meeting it. A vertex is even or odd according to its degree. The handshaking lemma says the degrees of all vertices add to twice the number of edges, so the number of odd-degree vertices is always even.
An Euler trail uses every edge exactly once. For a connected graph it exists if and only if there are exactly \(0\) or \(2\) vertices of odd degree. If there are two odd vertices, the trail must start at one and finish at the other.
An Euler circuit is a closed Euler trail: it uses every edge once and returns to the start. For a connected graph it exists if and only if every vertex has even degree (no odd vertices).
A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle also returns to its starting vertex. Note the contrast: Euler is about edges, Hamiltonian is about vertices, and a graph can have one without the other.
Let a connected graph have degrees \(\deg(v)\) at its vertices and \(E\) edges. The handshaking lemma links the two:
Write \(k\) for the number of vertices of odd degree. The two Euler tests are:
For a graph in which every one of \(n\) vertices has the same degree \(d\) (a regular graph), the handshaking lemma gives the edge count directly:
Testing a graph for Euler trails and circuits
- Check it is connected. If the graph is in separate pieces, no single trail can cover every edge.
- Find every degree and count the odd-degree vertices, \(k\). (Use \(\sum \deg(v) = 2E\) as a check — \(k\) must come out even.)
- Apply the Euler rule:
- \(k = 0\): an Euler circuit (and hence an Euler trail) exists.
- \(k = 2\): an Euler trail exists but no circuit; it must start and finish at the two odd vertices.
- \(k \ge 4\): neither an Euler trail nor an Euler circuit exists.
- For a Hamiltonian question, ignore degrees and instead try to trace a route that visits every vertex once (returning to the start for a cycle). A vertex that is the only link between two parts of the graph blocks any Hamiltonian cycle.
For the house-shaped graph above, the degrees are \(2, 2, 3, 3, 2\), so \(k = 2\): an Euler trail exists, running between the two odd vertices \(C\) and \(D\).
Find each degree, then add (handshaking check):
| \(\deg A,\ \deg B,\ \deg C,\ \deg D\) | \(=\) | \(3,\ 2,\ 3,\ 2\) |
| \(\sum \deg(v)\) | \(=\) | \(3+2+3+2 = 10\) |
| \(2E\) | \(=\) | \(2(5) = 10\ \checkmark\) |
Count the odd-degree vertices \(k\):
| \(\text{odd vertices}\) | \(=\) | \(A\ (3),\ C\ (3)\) |
| \(k\) | \(=\) | \(2\) |
Apply the Euler-trail rule \(k = 0\) or \(2\):
| \(k = 2\) | \(\Rightarrow\) | \(\text{Euler trail exists}\) |
| \(=\) | \(\text{start/finish at } A,\ C\) |
The degrees sum to \(10\); there are \(2\) odd vertices, so an Euler trail exists, starting and finishing at \(A\) and \(C\).
An Euler trail must begin and end at the odd vertices \(A\) and \(E\):
| \(\text{odd vertices}\) | \(=\) | \(A\ (1),\ E\ (1)\) |
| \(\text{trail}\) | \(:\) | \(A \to B \to C \to D \to B \to E\) |
Check every edge is used exactly once:
| \(\text{edges}\) | \(:\) | \(AB,\ BC,\ CD,\ DB,\ BE\) |
| \(\text{count}\) | \(=\) | \(5 = \text{all edges, once each}\) |
\(A \to B \to C \to D \to B \to E\) is an Euler trail: it uses all \(5\) edges exactly once and runs between the odd vertices \(A\) and \(E\).
(a) Euler circuit needs every vertex even:
| \(\deg A = \deg B = \deg D = \deg E\) | \(=\) | \(2\) |
| \(\deg C\) | \(=\) | \(4\) |
| \(k = 0\) | \(\Rightarrow\) | \(\text{Euler circuit exists}\) |
(b) Hamiltonian cycle must visit every vertex once and return:
| \(C\) | \(=\) | \(\text{only link between the two triangles}\) |
| \(\text{any full tour}\) | \(\Rightarrow\) | \(\text{must pass through } C \text{ twice}\) |
| \(\Rightarrow\) | \(\text{no Hamiltonian cycle}\) |
(a) Yes — every vertex is even, so an Euler circuit exists. (b) No — \(C\) is a cut vertex, so no Hamiltonian cycle is possible.
A single crossing of every bridge is an Euler trail; count the odd vertices:
| \(\text{degrees}\) | \(:\) | \(5,\ 3,\ 3,\ 3\) |
| \(\text{all four are odd}\) | \(\Rightarrow\) | \(k = 4\) |
Apply the Euler-trail rule (needs \(k = 0\) or \(2\)):
| \(k = 4 > 2\) | \(\Rightarrow\) | \(\text{no Euler trail}\) |
All four land masses have odd degree, so \(k = 4\). Since an Euler trail allows only \(0\) or \(2\) odd vertices, the seven bridges cannot all be crossed exactly once.
Common pitfalls
Frequently asked questions
What is the difference between a trail and a walk?
A walk is any sequence of connected edges. A trail is a walk with the extra condition that no edge is repeated (a vertex may still be revisited). A closed trail is a circuit.
When does a graph have an Euler trail?
A connected graph has an Euler trail if and only if it has exactly \(0\) or \(2\) vertices of odd degree. With two odd vertices the trail must start at one and finish at the other.
When does a graph have an Euler circuit?
A connected graph has an Euler circuit if and only if every vertex has even degree. It then uses every edge once and returns to its starting vertex.
What is the difference between an Euler trail and a Hamiltonian path?
An Euler trail uses every edge exactly once; a Hamiltonian path visits every vertex exactly once. They answer different questions and a graph may have either, both or neither.
Why is the Konigsberg bridge problem impossible?
The four land masses have degrees \(5, 3, 3\) and \(3\), so all four vertices are odd. An Euler trail allows only \(0\) or \(2\) odd vertices, and \(4 > 2\), so no walk can cross every bridge exactly once.
Can a graph have exactly one vertex of odd degree?
No. By the handshaking lemma the degrees add to \(2E\), which is even, so the odd degrees must pair up. The number of odd-degree vertices is always even.