Classical eulerian cycle algorithm

General information

Algorithmic problem: Eulerian cycle

Type of algorithm: recursion with an arbitrarily chosen start node[math]\displaystyle{ s\in V }[/math] as an additional input. Before the proper recursive procedure is invoked, the output sequence [math]\displaystyle{ S }[/math] is initialized so as to contain the start node [math]\displaystyle{ s }[/math] and nothing else.

Break condition: No edges/arcs leave the start node [math]\displaystyle{ s }[/math].

Induction basis

Abstract view: Nothing to do.

Induction step

In the following, both undirected edges and directed arcs are denoted by parentheses.

1. Let [math]\displaystyle{ p }[/math] be a (dynamically growing</math>) path, represented in [math]\displaystyle{ p }[/math] as an alternating sequence of nodes and edges/arcs.
2. Initialize so as to contain [math]\displaystyle{ s }[/math] and nothing else.
3. Set [math]\displaystyle{ x:=s }[/math].
4. While there are edges/arcs leaving [math]\displaystyle{ x }[/math]:
   1. Choose one such arc [math]\displaystyle{ (x,y) }[/math].
   2. Remove [math]\displaystyle{ (x,y) }[/math] from the graph.
   3. Append [math]\displaystyle{ (x,y) }[/math] and then [math]\displaystyle{ y }[/math] to [math]\displaystyle{ p }[/math].
   4. Set [math]\displaystyle{ x:=y }[/math].
5. If [math]\displaystyle{ x\neq s }[/math], terminate the algorithm with the statement that no Eulerian cycle exists.
6. Otherwise: For each node [math]\displaystyle{ v }[/math] on [math]\displaystyle{ p }[/math] that still has leaving edges/arcs,:
   1. Call the procedure recursively with [math]\displaystyle{ v }[/math] as the start node, giving path [math]\displaystyle{ p' }[/math].
   2. Replace [math]\displaystyle{ v }[/math] in [math]\displaystyle{ p }[/math] by [math]\displaystyle{ p' }[/math].

Correctness

Since each edge/arc is removed immediaely when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that the the order in which the nodes and edges/arcs occur in the output yields a correct path. Step 5 ensures that the path grows to a cycle, unless this is impossible. In that case no eulerian cycle exists because, obviously, the remaining graph is always Eulerian at the moment of a recursively call, if the original graph was Eulerian. In summary, it suffices to show all arcs are in the output.

Suppose for a contradiction that some edge/arc [math]\displaystyle{ e/a }[/math] is not in the output. Since the graph is (strongly) connected, there is a path [math]\displaystyle{ q }[/math] from the start node to the tail of [math]\displaystyle{ e/a }[/math] (an arbitrary endnode of [math]\displaystyle{ e/a }[/math] in the undirected case). Let [math]\displaystyle{ v }[/math] be the last node on [math]\displaystyle{ q }[/math] processed by any recursive call. Then the subsequent edge/arc on [math]\displaystyle{ q }[/math] has not been processed, which is impossible due to step 6.1

Complexity

Statement: Both for directed and undirected graphs, the asymtptotic complexity is [math]\displaystyle{ \mathcal{O}(n+m) }[/math], where [math]\displaystyle{ n }[/math] is the number of nodes and [math]\displaystyle{ m }[/math] the number of edges/ars.

Proof:

Remark: Of course, the edges/arcs need not be removed permanently. However, when an edge/arc is processed, it must be hidden from the algorithm up to its termination to achieve the linear bound on the complexity.