Eulerian and Hamiltonian Routes

Stage 23 of 23 Strand 3 of 5 3 lessons

3 illustrated lessons, each teaching the why before the how.

Jump to a lesson

Walks, Trails, Paths, Circuits and Cycles #

Five words for five different kinds of route.

A trail repeats no edge, a path repeats no vertex, and a circuit is a trail that closes

A walk is any sequence of edges, each one starting where the last ended. A-B-C-B uses the edge B to C twice.

A trail uses no edge twice. A-B-C-D-E-C passes through C twice, which is allowed.

A path uses no vertex twice: A-B-C-D-E, and no edge can repeat either.

A circuit is a trail that ends where it began: A-B-C-D-E-C-A.

A cycle is a circuit that repeats no vertex except the one at both ends: A-B-C-A.

Now you

In this graph, what is the route A-B-C-D-E-C-A?

In this graph, what is the route A-B-C-D-E?

Every edge once, and the degrees decide.

A graph has an Eulerian circuit exactly when it is connected and every degree is even

Can one trail use every edge exactly once? Count the degrees first: 2, 2, 4, 2, 2.

Every degree is even, and a trail does use all six edges and return: an Eulerian circuit.

One edge arrives and one leaves at each visit, so passing through needs an even degree.

Drop one edge and C and E have odd degree: exactly two odd vertices are left.

A trail still covers every edge, but it has to start at C and finish at E: an Eulerian trail.

With four odd vertices no trail can cover every edge: the bridges of Königsberg.

Now you

Does this graph have an Eulerian circuit?

A connected graph has exactly two vertices of odd degree. What follows?

Every vertex once, and no test to lean on.

A Hamiltonian cycle visits every vertex exactly once and returns to where it started

An Eulerian circuit uses every edge. A Hamiltonian cycle visits every vertex.

This route touches all five vertices once and closes: a Hamiltonian cycle.

Drop the closing edge and it is a Hamiltonian path: every vertex once, without returning to the start.

Here E has one edge, so a cycle through E would use that edge twice: none exists.

There is no degree test for a Hamiltonian cycle, so routes have to be tried one by one.

Now you

What is the marked route A-B-C-D-E-A?

What is the marked route A-B-C-D-E?