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) path, represented in [math]\displaystyle{ p }[/math] as an alternating sequence of nodes and edges/arcs.
2. Initialize [math]\displaystyle{ p }[/math] 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 immediately when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that 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 that 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 contradicts the procedure.

Complexity

Statement: Both for directed and undirected graphs, the asymtptotic complexity is linear in the number of edges/ars.

Proof: We assume that all data structures are implemented in the obvious appropriate way. First note that steps 1, 2, 3, and 5 take constant time each. The total number of iterations of steps 4 and 6, respectively, taken over all recursive calls, is linear in the number of edges/arcs.

Remarks:

1. Since the graph is (strongly) connected, the number of nodes is asymptotically dominated by the number of edges/arcs and, therefore, irrelevant here.
2. 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.