6.4.3 Obtaining an Euler Tour

Let G(N, A) be a connected graph with no nodes of odd degree. Then an Euler tour can be drawn on G in the following manner.

Euler-Tour Algorithm (Algorithm-6.4)

Begin at any desired starting node n₀ N and traverse successively the edges of G. keeping track of the route followed, and deleting from G each -edge of G as it is traversed. Do not, at any particular point in this procedure, traverse an edge that is an isthmus. (An isthmus is an edge whose deletion at that particular point in the procedure would divide the yet undeleted part of G into two separate nonempty components.) Continue this procedure until all edges of G have been deleted, at which point the traversed route is an Euler tour and you have returned to the starting node, n₀.

Example 6: Drawing an Euler Tour

We refer to the graph of Figure 6.14a. Assume that the starting node is node a. Suppose that we follow the route "a to b to g." At this point, edge (g, h) should not be traversed because it is an isthmus: if (g, h) is deleted, then the resulting undeleted part of G will consist of two separate nonempty components [edge (h, a) is separated from the rest of the undeleted part of G]. Thus, the next edge to be traversed should be either (g, j) or (g, f). The reader may wish to continue from here.

Algorithm 6.4 is very simple and convenient for manual applications. However, it is not particularly well suited for computer solutions. Whereas it is a trivial task for a human being to decide at each point whether a particular edge is or is not an isthmus, this is a time-consuming procedure for a computer. For that reason, alternative algorithms for obtaining Euler tours have been suggested for computer implementation. One of these algorithms, as we have already mentioned, is based on the procedure outlined in our earlier proof of Euler's theorem.

Exercise 6.4 Consider the procedure outlined in the proof of Euler's theorem and describe it in the form of a computer-programmable algorithm (possibly by drawing a flowchart).

From the description of Algorithm 6.4 it is clear that, in most cases, there exist many different Euler tours for any connected G(N, A) with no nodes of odd degree, in the sense that the routes followed in traversing all the edges of G are different However, all Euler tours of any given graph naturally have the same total length, equal to

The application of Algorithm 6.4 to finding an Euler path for graphs with two odd-degree nodes is also straightforward (one simply starts from one of the odd-degree nodes and ends up at the other).