Eulerian cycle

Definition

A Eulerian cycle is a cycle in a directed or undirected graph that contains each edge/arc exactly once.

Redundant information for clarification: In the directed case, each arc must have forward orientatin on the cycle.

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.

Known algorithms

Classical eulerian cycle algorithm

Normal example

• 
  Step 1
• 
  Step 2
• 
  Step 3
• 
  Step 4
• 
  Step 5
• 
  Step 6
• 
  Step 7
• 
  Step 8
• 
  Step 9
• 
  Step 10
• 
  Final Step

Another may well know Example

Contains 44 solutions