Charging Station: Generating All Eulerian Cycles

Iterative construction of every possible bypass graph

The inherent difficulty in generating all Eulerian cycles in a graph is keeping track of potentially many different alternatives at any given node. On the opposite end of the spectrum, a simple directed graph, a connected graph in which each node has indegree and outdegree equal to 1, offers a trivial case, since there is only one Eulerian cycle.

Our idea, then, is to transform a single labeled directed graph Graph containing $n ≥ 1$ Eulerian cycles to $n$ different simple directed graphs, each containing a single Eulerian cycle. This transformation has the property that it’s easily invertible, i.e., that given the unique Eulerian cycle in one of the simple directed graphs, we can easily reconstruct the original Eulerian cycle in Graph.

Given a node $v$ in Graph (of indegree greater than 1) with incoming edge ($u, v$) and outgoing edge ($v, w$), we’ll construct a “simpler” ($u, v, w$)-bypass graph in which we remove the edges ($u, v$) and ($v, w$) from Graph, and add a new node $x$ along with the edges ($u, x$) and ($x, w$) (figure below (top)).

The new edges ($u, x$) and ($x, w$) in the bypass graph inherit the labels of the removed edges ($u, v$) and ($v, w$), respectively. The critical property of this graph is revealed by the following exercise.