An Eulerian Path is a trail that uses every edge of a graph exactly once.

An Eulerian Circuit does the same but returns to its starting vertex.

The central idea is simple:

Eulerian problems are about edges.
Hamiltonian problems are about vertices.

Vertices may be visited more than once in an Eulerian trail, as long as each edge is used exactly once.

Eulerian Path

A valid Eulerian Path:

• uses every edge,
• uses each edge exactly once,
• may revisit vertices,
• does not need to return to the start.

Eulerian Circuit

A valid Eulerian Circuit additionally satisfies:

start = end

Eulerian vs Hamiltonian

Eulerian:

every Edge exactly once

Hamiltonian:

every Vertex exactly once

A Hamiltonian path may ignore most graph edges. An Eulerian path must consume all edges.

The Königsberg bridges

The classical Seven Bridges of Königsberg problem asked whether one could walk through the city while crossing each bridge exactly once.

Euler modeled land regions as vertices and bridges as edges and proved that the requested walk was impossible.

This work is widely regarded as foundational to graph theory.

Undirected graphs: degree conditions

For an undirected graph, an Eulerian Circuit exists when:

1. all non-isolated vertices belong to one connected component,
2. every vertex has even degree.

An Eulerian Path but not a Circuit exists when:

1. all non-isolated vertices are connected,
2. exactly two vertices have odd degree.

Therefore:

0 odd vertices → Eulerian Circuit
2 odd vertices → Eulerian Path
>2 odd vertices → no Eulerian trail

Why do odd degrees matter?

At an internal vertex of a trail, edges are normally consumed in pairs:

enter + leave

Only the start and end of an open Eulerian Path can have an unmatched entry or exit, which explains the two odd-degree vertices.

Connectivity check

Isolated vertices do not matter when the objective is to use all existing edges.

We only need the part of the graph containing edges to be connected.

function isConnectedIgnoringIsolated(graph) {
  const nodes = Object.keys(graph);

  const start = nodes.find(
    node => (graph[node]?.length ?? 0) > 0
  );

  if (!start) return true;

  const visited = new Set();
  const stack = [start];

  while (stack.length) {
    const node = stack.pop();

    if (visited.has(node)) continue;

    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        stack.push(next);
      }
    }
  }

  return nodes.every(node => {
    const degree = graph[node]?.length ?? 0;
    return degree === 0 || visited.has(node);
  });
}

Detecting the Eulerian type

function getEulerianType(graph) {
  if (!isConnectedIgnoringIsolated(graph)) {
    return "NONE";
  }

  let oddCount = 0;

  for (const node of Object.keys(graph)) {
    if ((graph[node]?.length ?? 0) % 2 !== 0) {
      oddCount++;
    }
  }

  if (oddCount === 0) return "CIRCUIT";
  if (oddCount === 2) return "PATH";

  return "NONE";
}

Hierholzer's algorithm

Once existence is established, Hierholzer's algorithm can construct the trail efficiently.

The idea is:

1. start from a valid start vertex,
2. repeatedly follow an unused edge,
3. remove or mark each edge as it is used,
4. when the current vertex has no unused outgoing edge, append it to the result,
5. backtrack through the stack,
6. reverse the result.

Directed JavaScript implementation

function eulerTrailDirected(graph, start) {
  const g = Object.fromEntries(
    Object.entries(graph).map(
      ([node, edges]) => [node, [...edges]]
    )
  );

  const stack = [start];
  const path = [];

  while (stack.length > 0) {
    const current = stack[stack.length - 1];

    if ((g[current]?.length ?? 0) > 0) {
      const next = g[current].pop();
      stack.push(next);
    } else {
      path.push(stack.pop());
    }
  }

  return path.reverse();
}

Undirected implementation detail

In an undirected adjacency list, an edge usually appears twice:

A: [B]
B: [A]

Using A → B must therefore remove both adjacency entries.

function eulerTrailUndirected(graph, start) {
  const g = Object.fromEntries(
    Object.entries(graph).map(
      ([node, edges]) => [node, [...edges]]
    )
  );

  const stack = [start];
  const path = [];

  while (stack.length > 0) {
    const current = stack[stack.length - 1];

    if ((g[current]?.length ?? 0) > 0) {
      const next = g[current].pop();

      const reverseIndex =
        g[next]?.indexOf(current) ?? -1;

      if (reverseIndex !== -1) {
        g[next].splice(reverseIndex, 1);
      }

      stack.push(next);
    } else {
      path.push(stack.pop());
    }
  }

  return path.reverse();
}

For multigraphs, unique edge IDs are safer than removing neighbors by value.

Choosing the start vertex

For an Eulerian Circuit, start at any non-isolated vertex.

For an Eulerian Path with exactly two odd vertices, start at one of the odd vertices.

function findEulerStart(graph) {
  const nodes = Object.keys(graph);

  const oddNodes = nodes.filter(
    node => (graph[node]?.length ?? 0) % 2 !== 0
  );

  if (oddNodes.length === 2) {
    return oddNodes[0];
  }

  return nodes.find(
    node => (graph[node]?.length ?? 0) > 0
  ) ?? nodes[0];
}

Directed graph conditions

Directed graphs use in-degree and out-degree instead of a single degree.

For an Eulerian Circuit, every active vertex must satisfy:

inDegree(v) = outDegree(v)

with suitable connectivity.

For an Eulerian Path:

• one start vertex satisfies:

outDegree = inDegree + 1

• one end vertex satisfies:

inDegree = outDegree + 1

• every other active vertex satisfies:

inDegree = outDegree

Complexity

With an efficient edge representation, Hierholzer processes each edge once.

Typical complexity:

Time:  O(V + E)
Space: O(V + E)

It is therefore dramatically cheaper than Hamiltonian backtracking.

Hierholzer vs Fleury

Fleury's algorithm follows the rule:

avoid using a bridge unless no alternative exists.

It is intuitive but repeated bridge checks can make it slower.

Hierholzer constructs and merges cycles naturally and is usually preferred for efficient implementations.

Real-world applications

Street sweeping

Intersections can be vertices and streets can be edges. If all streets should be traversed exactly once, the model is Eulerian.

Route inspection

Pipes, cables, roads, and infrastructure links may need complete edge coverage.

Network-link inspection

If every network connection rather than every node must be tested, an edge-based model is appropriate.

DNA sequence assembly

de Bruijn graph formulations of sequence assembly are strongly connected to Eulerian paths, where edges encode sequence overlap structure.

Drawing puzzles

"Draw the entire figure without lifting the pen or retracing a line" is essentially an Eulerian-trail question.

Chinese Postman Problem

Real networks are not always Eulerian.

The Chinese Postman Problem asks for the minimum-cost closed walk that covers every edge at least once.

The difference is:

Eulerian:
every edge exactly once

Chinese Postman:
every edge at least once
+ minimize repeated travel

Important edge cases

• isolated vertices,
• graphs with no edges,
• self-loops,
• parallel edges,
• disconnected edge-bearing components,
• directed graphs,
• incorrect deletion of undirected edges.

Comparison

| Problem | Focus | Exactly once | Return to start | Optimization | |---|---|---|---|---| | Eulerian Path | Edge | Edge | No | No | | Eulerian Circuit | Edge | Edge | Yes | No | | Hamiltonian Path | Vertex | Vertex | No | No | | Hamiltonian Cycle | Vertex | Vertex | Yes | No | | TSP | Vertex | Vertex | Yes | Minimum cost | | Chinese Postman | Edge | At least once | Usually yes | Minimum cost |

When should you use Eulerian algorithms?

Use them when every edge must be covered and revisiting vertices is acceptable.

When are they not a good fit?

Use Hamiltonian models when every vertex must be used exactly once.

Use shortest-path algorithms for endpoint-to-endpoint optimization.

Use TSP for a minimum-cost tour through vertices.

Use Chinese Postman when every edge must be covered but repetition is allowed and should be minimized.

Summary

Eulerian Path uses every edge exactly once.

Eulerian Circuit does the same and returns to its starting vertex.

For undirected graphs:

0 odd-degree vertices → Eulerian Circuit
2 odd-degree vertices → Eulerian Path
more than 2 → no Eulerian trail

Connectivity of all non-isolated vertices is also required.

For directed graphs, the balance between in-degree and out-degree is the key condition.

Hierholzer's algorithm constructs Eulerian trails efficiently in O(V + E) time.

The most useful recognition rule is simple:

cover every edge → Eulerian
visit every vertex once → Hamiltonian