What is it?

In graph theory, an Eulerian path (or Eulerian trail) is a path through a graph that visits every edge exactly once. It's named after Leonhard Euler, who solved the famous Seven Bridges of Königsberg problem in 1736 — the birth of graph theory.

In this cipher, you're given a graph where each vertex is labeled with a letter. The Eulerian path that visits every edge exactly once traces a sequence of vertex labels. Those labels, in order, spell the answer word.

Concrete Example

Consider this graph with 4 vertices labeled N, O, D, E:

N — O    (edge 0)
O — D    (edge 1)
D — E    (edge 2)
N — E    (edge 3)

Degree of each vertex: N=2, O=2, D=2, E=2. Since all degrees are even, an Eulerian path exists (and it's actually an Eulerian circuit — it starts and ends at the same vertex).

One Eulerian path: N → O → D → E → N
Edge order: (N-O), (O-D), (D-E), (E-N)

Vertex labels in path order: N, O, D, E, N → "NODEN"

But we only read the unique vertex sequence along the path: N, O, D, E → "NODE".

If the degree sequence has exactly two odd-degree vertices, the path must start at one odd vertex and end at the other. For example, if degree sequence is N=3, O=2, D=2, E=1, the Eulerian path would start at N or E.

Why It Works

Euler proved that an Eulerian path exists in a connected graph if and only if 0 or 2 vertices have odd degree. This is known as Euler's theorem. Since the graph is constructed from a word's letter sequence, the path through the graph's vertices in order naturally reconstructs that word. The added extra edges create complexity but don't change the fundamental Eulerian property, making the puzzle challenging but solvable.

Solving Tips

• First, check vertex degrees — if 0 odd-degree vertices, any starting point works (Eulerian circuit)
• If exactly 2 odd-degree vertices, the path must start at one and end at the other
• Use Fleury's algorithm or Hierholzer's algorithm to find the path
• Follow edges one by one, never using a bridge unless forced
• The sequence of vertex labels along the path spells the answer

Real-World Applications

• Route planning: Garbage trucks, snow plows, and postal carriers use Eulerian paths to cover every street exactly once (the Chinese Postman Problem)
• DNA sequencing: The de Bruijn graph approach to genome assembly uses Eulerian paths to reconstruct DNA sequences from fragments
• Printed circuit board design: Etching traces that cover all connections without lifting the pen is an Eulerian path problem
• Network testing: Testing every link in a network by tracing an Eulerian path minimizes travel time
• Maze solving: The "right-hand rule" for solving mazes is essentially finding an Eulerian path through the maze graph