Leonard Euler’s Bridges of Konigsberg Problem

The map below shows the bridges over the historic city of Konigsberg, which Euler referred to when developing Graph Theory.

• 1.) Can a tour be made of the town which returns to the original point after crossing every bridge exactly once?
• 2.) Euler determined that such a tour would be possible if either one bridge was removed or added.
  • Which bridge would you remove?
  • Where would you add a bridge?

In real life, it is often necessary to traverse every edge of a graph – for instance, somebody delivering marketing material in a neighbourhood would need to traverse every street – to minimise the time the job takes it is preferable to traverse each street only once.

A Eulerian circuit is a circuit which traverses every edge exactly once.

An Eulerian trail is a trail which traverses every edge exactly once, but does not start and end at the same vertex.

For instance, on the left A -> B -> C -> B -> E -> C -> D -> E -> A is an Eulerian circuit and on the right, A -> B -> C -> A -> E -> D -> C is an Eulerian trail.

If a graph contains an Eulerian circuit we call it Eulerian, whereas if it contains an Eulerian trail but not an Eulerian circuit we call it semi-Eulerian.

An easier way to test if a graph is Eulerian considers the degree of its vertices.

In order for a connected graph to be Eulerian, it must not have any vertices of odd degree.

A connected graph is semi-Eulerian if there are exactly two vertices of odd degree. The Eulerian trail starts at one one of these vertices and ends at the other.

Worked Example

• Show that the graph below is semi-Eulerian;
• Find an Eulerian trail;
• Add an edge so that the resulting graph is Eulerian. Find an Eulerian circuit in this case.

Exercise

Answers