Eulerian and Hamiltonian Paths

Can a snowplough clear every street in a neighbourhood without driving any street twice? Can a delivery van visit every customer exactly once and get back to the depot? The first question is about using every edge once (an Eulerian trail); the second is about visiting every vertex once (a Hamiltonian cycle). They sound alike, but one has a quick test and the other doesn’t.

Key ideas

Walks, trails, paths, circuits and cycles

All of these are ways of moving through a graph along edges. They differ in what is allowed to repeat:

Name	What it is	Repeated edges?	Repeated vertices?
Walk	Any sequence of edges, each starting where the last ended	Allowed	Allowed
Trail	A walk with no repeated edges	No	Allowed
Path	A walk with no repeated vertices	No	No
Circuit	A trail that starts and finishes at the same vertex	No	Allowed
Cycle	A circuit with no repeated vertices, apart from the start and finish	No	Only start = finish

Every path is a trail, and every trail is a walk. Every cycle is a circuit. We write routes as lists of vertices, such as A–B–D–E.

Eulerian trails and circuits

An Eulerian trail uses every edge exactly once. An Eulerian circuit is an Eulerian trail that finishes where it started. (A graph with an Eulerian circuit is called Eulerian; one with an Eulerian trail but no circuit is semi-Eulerian.)

Each time a trail passes through a vertex, it uses two edges there: one in, one out. So at every vertex except the start and finish, the edges pair up and the degree must be even. That gives a quick test for a connected graph:

Odd vertices	Result
$0$	Eulerian circuit (you can start anywhere)
$2$	Eulerian trail but no circuit: it must start at one odd vertex and finish at the other
$4$ or more	No Eulerian trail

(The number of odd vertices is always even, by the handshake lemma.)

This is how Euler solved the famous “Bridges of Königsberg” puzzle in 1736: the four land areas each had an odd number of bridges, so no walk could cross every bridge exactly once.

Graph 1 has all even vertices. Graph 2 (no edge CA) has exactly two odd vertices, A and C.

Hamiltonian paths and cycles

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle visits every vertex exactly once and returns to the start. It doesn’t need to use every edge.

Unlike the Eulerian case, there’s no simple test for whether a Hamiltonian cycle exists. You find one by trial, or argue why none can exist. Some useful facts:

A vertex of degree $1$ can’t be on a Hamiltonian cycle (you’d have no way out after arriving), so then there’s no Hamiltonian cycle.
A complete graph $K_n$ with $n \ge 3$ always has a Hamiltonian cycle: visit the vertices in any order.
If removing one vertex splits the graph into separate pieces, there’s no Hamiltonian cycle, because the cycle would have to pass through that vertex twice.

Hamiltonian cycles are what the travelling salesman problem is about; Eulerian circuits lead to the Chinese postman problem.

Worked examples

Example 1: Naming types of route

In graph 1, say whether each route is a walk, trail, path, circuit or cycle. Give the most specific name.

(a) A–B–C–A–B
(b) B–D–E–B–C
(c) A–B–D–E
(d) B–D–E–C–B
(e) A–B–D–E–B–C–A

Solution.

(a) Edge AB is used twice, so it’s only a walk.

(b) No edge repeats, but vertex B appears twice, so it’s a trail (not a path).

(d) It returns to B, uses no edge twice, and no other vertex repeats: a cycle.

(e) It returns to A and uses no edge twice, but passes through B twice: a circuit (not a cycle).

Example 2: An Eulerian circuit

Show that graph 1 has an Eulerian circuit, and find one starting at A.

Solution. The graph is connected. The degrees are A $2$ , B $4$ , C $4$ , D $2$ , E $4$ and F $2$ : all even, so an Eulerian circuit exists.

Build it by walking and crossing off edges as you use them. One answer:

\text{A–B–D–E–B–C–E–F–C–A}

Check: it uses $9$ edges (AB, BD, DE, EB, BC, CE, EF, FC, CA), which are all $9$ edges of the graph, each once, and it ends at A.

Example 3: An Eulerian trail

Graph 2 is graph 1 without edge CA. Does it have an Eulerian circuit? An Eulerian trail? If there’s a trail, find one.

Solution. Now A has degree $1$ and C has degree $3$ ; every other vertex is even. With exactly two odd vertices there’s no Eulerian circuit, but there is an Eulerian trail, which must start at A and finish at C (or the reverse).

\text{A–B–D–E–B–C–E–F–C}

Check: $8$ edges, all different, which is every edge of graph 2.

Example 4: Hamiltonian cycles

(a) Find a Hamiltonian cycle in graph 1.
(b) Explain why graph 2 has no Hamiltonian cycle, and find a Hamiltonian path.

Solution. (a) A–B–D–E–F–C–A visits each of the six vertices once and returns to A. Every step is an edge of the graph (AB, BD, DE, EF, FC, CA).

(b) In graph 2, vertex A has degree $1$ . A cycle arriving at A would have no unused edge to leave by, so no Hamiltonian cycle exists. A Hamiltonian path can start at A: A–B–D–E–F–C visits every vertex exactly once.

Common mistakes

Mixing up Eulerian and Hamiltonian. Eulerian means every edge once; Hamiltonian means every vertex once. A memory hook: Euler, Edges.

Starting an Eulerian trail at the wrong vertex. With exactly two odd vertices, the trail must start at one of them and finish at the other. Start anywhere else and you’ll get stuck with edges left over.

Forgetting to check that the graph is connected. The degree test only works for a connected graph. Two separate pieces, each with all even degrees, still have no Eulerian circuit.

Calling a circuit a cycle. A circuit may pass through a vertex more than once (like A–B–D–E–B–C–A). A cycle can’t, except for returning to the start.

Looking for a degree test for Hamiltonian cycles. There isn’t one. Show a cycle if you find one; to show there’s none, give a reason such as a vertex of degree $1$ .

Practice

1. (Warm-up) In the complete graph $K_4$ with vertices P, Q, R, S, give the most specific name (walk, trail, path, circuit, cycle) for each route: (a) P–Q–R–P–S, (b) P–Q–R–S, (c) P–Q–R–S–P.

Solution

(a) No edge repeats but P appears twice, and it doesn’t return to the start: a trail.

(b) No vertex repeats: a path (in fact a Hamiltonian path).

2. (Warm-up) Three connected graphs have these degrees. Which has an Eulerian circuit, which has an Eulerian trail only, and which has neither?

(a) $2, 4, 4, 2, 2$
(b) $3, 3, 2, 2$
(c) $3, 3, 3, 3$

Solution

(a) No odd vertices: Eulerian circuit.

(b) Two odd vertices: an Eulerian trail (starting and finishing at the two vertices of degree $3$ ), but no circuit.

3. (Warm-up) Does $K_5$ have an Eulerian circuit? Does $K_4$ ?

Solution

In $K_5$ every vertex has degree $4$ , which is even, so yes. In $K_4$ every vertex has degree $3$ : four odd vertices, so $K_4$ has no Eulerian circuit (and no Eulerian trail).

4. (Core) A town has four districts W, X, Y, Z joined by bridges: two between W and X, two between W and Y, and one each between W and Z, X and Z, Y and Z, and X and Y.

(a) Can a tourist walk across every bridge exactly once? If so, where must the walk start and finish?
(b) The council wants a walk that crosses every bridge once and returns to its start. Between which two districts should one new bridge be built?

Solution

(a) Model districts as vertices and bridges as edges. Degrees: W $2 + 2 + 1 = 5$ , X $2 + 1 + 1 = 4$ , Y $2 + 1 + 1 = 4$ , Z $1 + 1 + 1 = 3$ . Exactly two odd vertices (W and Z), so yes: the walk must start at W and finish at Z, or the reverse.

(b) Build a bridge between W and Z. Then W has degree $6$ and Z has degree $4$ , every vertex is even, and an Eulerian circuit exists.

5. (Core) A graph has vertices A, B, C, D, E and edges AB, AC, BC, BD, CD, CE, DE and BE. Explain why it has an Eulerian trail but no Eulerian circuit, and find an Eulerian trail.

Solution

Degrees: A $2$ , B $4$ , C $4$ , D $3$ , E $3$ . The graph is connected with exactly two odd vertices, D and E, so there’s an Eulerian trail from D to E but no circuit.

One trail: D–B–A–C–B–E–C–D–E. It uses DB, BA, AC, CB, BE, EC, CD, DE: all $8$ edges, each once.

6. (Core) List all the different Hamiltonian cycles in $K_4$ (vertices P, Q, R, S). Treat a cycle as the same if it only has a different starting point or direction.

Solution

Start every cycle at P. The other three vertices can be arranged in $3! = 6$ orders, but each cycle appears twice (once in each direction), giving $3$ cycles:

P–Q–R–S–P
P–Q–S–R–P
P–R–Q–S–P

7. (Core) Two triangles share one vertex: vertices A, B, C, D, E with edges AB, BC, CA, CD, DE, EC.

(a) Show that the graph has an Eulerian circuit.
(b) Explain why it has no Hamiltonian cycle.

Solution

(a) Degrees: A $2$ , B $2$ , C $4$ , D $2$ , E $2$ . All even and the graph is connected, so there’s an Eulerian circuit, for example C–A–B–C–D–E–C.

(b) Removing C splits the graph into two pieces (A, B and D, E). A Hamiltonian cycle would have to pass through C to get from one piece to the other and again to come back, visiting C twice. So there’s no Hamiltonian cycle.

8. (Challenge) A connected graph has exactly four odd vertices.

(a) What is the least number of extra edges you need to add so that it has an Eulerian trail? An Eulerian circuit?
(b) For which values of $n$ does $K_n$ (with $n \ge 2$ ) have an Eulerian circuit?

Solution

(a) An edge joining two odd vertices makes both of them even. One extra edge leaves two odd vertices, which is enough for an Eulerian trail. Two extra edges, each joining a different pair of the odd vertices, leave none, which gives an Eulerian circuit. You can’t do better, since one edge changes the degree of only two vertices.

(b) Every vertex of $K_n$ has degree $n - 1$ . That’s even exactly when $n$ is odd, so $K_n$ has an Eulerian circuit for $n = 3, 5, 7, \dots$ (odd $n$ ).

9. (Challenge) Explain why, if a connected graph has an Eulerian circuit, every vertex must have even degree.

Solution

Follow the circuit. Every time it passes through a vertex, it arrives along one edge and leaves along a different edge, using up $2$ of that vertex’s edges. The starting vertex is also paired up: the first edge out of it pairs with the last edge back in. Since the circuit uses every edge exactly once, the edges at each vertex are split into these pairs, so every degree is even.