Eulerian Path

Run Hierholzer stack traversal, consume every edge once, and append vertices while dead ends unwind.

Core idea

Hierholzer's algorithm walks unused edges until it reaches a dead end. Dead-end vertices are appended while the stack unwinds, automatically splicing every discovered cycle into one trail.

Read the visualization

Remaining-degree badges shrink as edges are consumed. The traversal stack records the live walk, and backtracking builds the answer in reverse order.

Load the connected graph and the requirement to use every edge exactly once.

1function eulerPath(n: number, edges: [number, number][]): number[] {
const adj = Array.from({ length: n }, () => [] as { v: number; eid: number }[]);
edges.forEach(([u, v], i) => { adj[u].push({ v, eid: i }); adj[v].push({ v: u, eid: i }); });
const deg = adj.map((a) => a.length);
const odd = [...Array(n).keys()].filter((u) => deg[u] % 2 === 1);  //  verdict:  odd-degree vertex  0/2
if (odd.length !== 0 && odd.length !== 2) return [];
const start = odd.length ? odd[0]: 0;         // check odd-degree vertex check from check
const used = new Array(edges.length).fill(false);
const stack = [start];
const path: number[] = [];
while (stack.length) {
  const u = stack[stack.length - 1];
  const next = adj[u].find((e) => !used[e.eid]);
  if (next) {
    used[next.eid] = true;                     // walk edge: walk edge  + walk stack 
    stack.push(next.v);
  } else {
    stack.pop();                               // back: back stack back path 
    path.push(u);
  }
}
return path.reverse();                         // done pop order done Eulerian  path 
23}

stack: ( empty)
path: ( empty)
target: 7 count edge visit each once

Complexity and tradeoffs

Time: O(V+E). Space: O(V+E). Connectivity and odd-degree conditions determine whether an undirected Eulerian trail exists.

Invariant: Every consumed edge appears exactly once in the unfinished stack walk or the reversed output suffix.

Where it fits

Eulerian trails model route inspection, DNA assembly with de Bruijn graphs, and reconstruction from adjacent pairs. Hamiltonian paths instead require visiting vertices once and are much harder.