Eulerian cycle
Definition
- A eulerian cycle is an ordinary cycle in a directed or undirected graph that contains each edge/arc exactly once.
- A directed or undirected graph is called eulerian if it admits a eulerian cycle.
Remark: It is easy to see (and follows from the classical algorithm) that a graph [math]\displaystyle{ G }[/math] is eulerian if, and only if:
- Undirected case: [math]\displaystyle{ G }[/math] is connected, and each node has even degree.
- Directed case: [math]\displaystyle{ G }[/math]is strongly connected, and for each node [math]\displaystyle{ v }[/math], the in degree of [math]\displaystyle{ v }[/math] equals the out degree of [math]\displaystyle{ v }[/math].
Input
A strongly connected directed or connected undirected graph.
Output
A eulerian cycle as an alternating sequence of nodes and edges/arcs or, alternatively, the (correct) message that no such cycle exists.