Eulerian and Hamiltonian Circuits

Two Practical Problems

Seven bridge problem Two islands surrounded by a river are connected to each other and the riverbanks by seven bridges as shown below

Then is it possible to walk over each bridge exactly once, starting from one of the locations A, B, C, D and ending at the same location? If we use vertices to denote the locations and edges to denote bridges, then the map is simplified to the graph on the right

Travelling salesman problem Suppose the distances between each pair of the cities A, B, C and D are given, and suppose a salesman must travel to each city exactly once, starting and ending at city A. Which route from city to city will minimize the total travelling distance? If we use vertices to denote cities, and put the distance between any two cities on the edge joining them, then we can represent the given knowledge by the following weighted graph

Before considering the above two problems in detail, we first introduce below a few related basic terminology.

Eulerian and Hamiltonian Paths and Circuits

A circuit is a walk that starts and ends at a same vertex, and contains no repeated edges.

An Eulerian circuit in a graph G is a circuit that includes all vertices and edges of G. A graph which has an Eulerian circuit is an Eulerian graph.

A Hamiltonian circuit in a graph G is a circuit that includes every vertex (except first/last vertex) of G exactly once.

An Eulerian path in a graph G is a walk from one vertex to another, that passes through all vertices of G and traverses exactly once every edge of G. An Eulerian path is therefore not a circuit.

A Hamiltonian path in a graph G is a walk that includes every vertex of G exactly once. A Hamiltonian path is therefore not a circuit.

Examples

1. In the following graph

   

   (a)

   Walk v₁e₁v₂e₃v₃e₄v₁, loop v₂e₂v₂ and vertex v₃ are all circuits, but vertex v₃ is a trivial circuit.

   (b)

   v₁e₁v₂e₂v₂e₃v₃e₄v₁ is an Eulerian circuit but not a Hamiltonian circuit.

   (c)

   v₁e₁v₂e₃v₃e₄v₁ is a Hamiltonian circuit, but not an Eulerian circuit.

2. K₃ is an Eulerian graph, K₄ is not Eulerian.
3. Graph

   

   has an Eulerian path but is not Eulerian.

Euler's Theorem Let G be a connected graph.

(i)

G is Eulerian, i.e. has an Eulerian circuit, if and only if every vertex of G has even degree.

(ii)

G has an Eulerian path, but not an Eulerian circuit, if and only if G has exactly two vertices of odd degree. The Eulerian path in this case must start at any of the two odd-degree vertices and finish at the other vertex.

Proof We only consider the case (i).

(a)

We first show G is Eulerian implies all vertices have even degree.

Let C be an Eulerian (circuit) path of G and v an arbitrary vertex. Then each edge in C that enters v must be followed by an edge in C that leaves v. Thus the total number of edges incident at v must be even.

(b)

We then show by induction that G is Eulerian if all of its vertices are of even degree.

Let S_n be the statement that connected graph of n vertices must be Eulerian if its every vertex has even degree.

For n=1, G is either a single vertex or a single vertex with loops. Hence S₁ is true because an Eulerian circuit can be obtained by traversing all loops (if any) one by one.

For inductions we now assume S_k is true, and G has k+1 vertices. Select a vertex v of G. We form a subgraph G' with one vertex less as follows: remove all loops of v and break all remaining edges incident at v; remove v and connect in pairs the broken edges in such a way G remains connected. Since the degrees of the vertices remain even when G is reduced to G', the induction assumption implies the existence of an Eulerian circuit of G'. The Eulerian circuit of G can thus be constructed by traversing all loops (if any) at v and then the Eulerian circuit of G' starting and finishing at v. Hence G is Eulerian and S_k+1 is true, implying S_n is true for all n 1. For clarity and intuitiveness, the induction step is exemplified by the following graphs

Examples

4. Due to the above Euler's theorem, the seven bridge problem described earlier has no solution, i.e. the graph in the problem does not have an Eulerian circuit because all vertices there (A, B, C, D) have odd degrees.
5. As for the travelling salesman problem, we need to find all the Hamiltonian circuits for the graph, calculate the respective total distance and then choose the shortest route.
   

   route		total distance
   A B C D A	30 + 30 + 25 + 40 = 125
   A B D C A	140
   A C B D A	155
   A C D B A	140
   A D B C A	155
   A D C B A	125

   Hence the best route is either ABCDA or ADCBA.

Fleury's Algorithm for Finding Eulerian Path or Circuit

(i)

If there are odd degree vertices (there then must be exactly two if an Eulerian path is to exist), choose one. Travel over any edge whose removal will not result in breaking the graph into disconnected components.

(ii)

Rub out the edge (or colour the edge if you like) you have just traversed, and then travel over any remaining edge whose removal will not result in breaking the remaining subgraph into disconnected components.

(iii)

Repeat (ii) until other edges are rubbed out or coloured.

Example

6. Find an Eulerian path for the graph G below

   

   We start at v₅ because (v₅) = 5 is odd. We can't choose edge e₅ to travel next because the removal of e₅ breaks G into 2 connected parts. However we can choose e₆ or e₇ or e₉. We choose e₆. One Eulerian path is thus