# Charging Station: Generating All Eulerian Cycles

Let’s learn how to generate Eulerian cycles in graphs.

## We'll cover the following

## 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.

Get hands-on with 1200+ tech skills courses.