MO640 - Exercises - Informatics Concepts, Setubal and Meidanis 1997 - chapter 2

Exercises marked with (*) require further reading/search beyond the suggested texts.

6. It is known that a graph has an Eulerian path if and only if it is connected (except for possible isolated vertices), and exactly two vertices have odd degree. Based on this observation, propose an algorithm that finds an Eulerian path in a graph if such a path exists.

Answer:

Pick a vertex with odd degree [if there are any. If not, pick an arbitrary vertex] to be the current vertex.
An edge from the current vertex is chosen to be next in the path if its deletion won't increase the number of nontrivial connected components in the graph, unless there's no such edge. If that's the case, the algorithm stops [failure].
Move to the other endpoint of the vertex, which will be the new current vertex, and delete the chosen edge.
If there are no edges left, stop [success]. Otherwise, keep traversing the graph as above.

The sequence of traversed edges form the Eulerian path. If all vertices have even degree then the procedure above will yield an Eulerian cycle or tour.

References:
Wikipedia: Eulerian path
Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms. 2nd edition. Problem 22-3.

MO640 Home