9.18 Euler Paths

You need to traverse every edge in a graph exactly once.

algorithmsgraphsgraph-theory

9.18 Euler Paths

Problem

You need to traverse every edge in a graph exactly once.

Some problems care about edges rather than vertices. A delivery route may need to use every street segment. A drawing puzzle may require tracing every line without lifting the pen. A network diagnostic tool may need to test every link. A genome assembly algorithm may need to walk through every overlap edge.

You need to determine whether such a traversal exists and, if it does, construct it.

Solution

Use Euler path conditions and Hierholzer's algorithm.

An Euler path is a path that uses every edge exactly once.

An Euler circuit is an Euler path that starts and ends at the same vertex.

Example:

A -- B
|    |
D -- C

An Euler circuit exists:

A → B → C → D → A

Every edge is used once, and the path returns to the starting vertex.

Discussion

Euler paths are different from ordinary graph paths.

A standard path usually avoids repeating vertices.

An Euler path may revisit vertices many times.

The restriction is on edges:

Each edge must be used exactly once.

This changes the problem completely.

For example:

A -- B -- C

has an Euler path:

A → B → C

but not an Euler circuit, because the path starts at A and ends at C.

Undirected Euler Conditions

For an undirected graph, degrees determine whether an Euler traversal exists.

Graph Property Euler Result
All non-isolated vertices connected and 0 odd-degree vertices Euler circuit
All non-isolated vertices connected and 2 odd-degree vertices Euler path
Otherwise No Euler path

The odd-degree rule is the key.

In an Euler traversal, every time you enter a vertex, you usually leave it through a different unused edge. This pairs incident edges. Therefore most vertices must have even degree.

Only the start and end vertices of an open Euler path may have odd degree.

Example: Euler Circuit

Consider:

A -- B
|    |
D -- C

Degrees:

Vertex Degree
A 2
B 2
C 2
D 2

All degrees are even.

An Euler circuit exists.

Example: Euler Path

Consider:

A -- B -- C

Degrees:

Vertex Degree
A 1
B 2
C 1

There are exactly two odd-degree vertices.

An Euler path exists, starting at one odd vertex and ending at the other.

Valid path:

A → B → C

Example: No Euler Path

Consider:

    A
   /|\\n  B C D

Degrees:

Vertex Degree
A 3
B 1
C 1
D 1

There are four odd-degree vertices.

No Euler path exists.

Recipe: Test Undirected Euler Type

def euler_type_undirected(graph):
    odd = [
        vertex
        for vertex, neighbors in graph.items()
        if len(neighbors) % 2 == 1
    ]

    if len(odd) == 0:
        return "circuit"

    if len(odd) == 2:
        return "path"

    return "none"

This only checks degrees. A complete implementation must also verify connectivity among non-isolated vertices.

Connectivity Requirement

Degree conditions are not enough.

Consider:

A -- B

C -- D

Degrees:

Vertex Degree
A 1
B 1
C 1
D 1

There are four odd vertices, so no Euler path exists.

Now consider:

A -- B -- A

C -- D -- C

Each component may satisfy local degree conditions, but no single traversal can cover both components because the graph is disconnected.

Euler traversal requires all non-isolated vertices to belong to one connected component.

Recipe: Check Non-Isolated Connectivity

def connected_non_isolated(graph):
    start = None

    for vertex, neighbors in graph.items():
        if neighbors:
            start = vertex
            break

    if start is None:
        return True

    visited = set()

    def dfs(vertex):
        visited.add(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)

    dfs(start)

    for vertex, neighbors in graph.items():
        if neighbors and vertex not in visited:
            return False

    return True

Now combine the checks:

def has_euler_path_undirected(graph):
    if not connected_non_isolated(graph):
        return False

    return euler_type_undirected(graph) != "none"

Hierholzer's Algorithm

Once the conditions are satisfied, construct the path with Hierholzer's algorithm.

The idea is:

  1. Follow unused edges until stuck.
  2. Add vertices to the output while backtracking.
  3. Reverse the output.

For undirected graphs, each edge must be removed from both endpoint lists.

def euler_path_undirected(graph):
    graph = {
        vertex: neighbors[:]
        for vertex, neighbors in graph.items()
    }

    odd = [
        vertex
        for vertex, neighbors in graph.items()
        if len(neighbors) % 2 == 1
    ]

    if len(odd) == 2:
        start = odd[0]
    else:
        start = next(
            (
                vertex
                for vertex, neighbors in graph.items()
                if neighbors
            ),
            None
        )

    if start is None:
        return []

    stack = [start]
    path = []

    while stack:
        vertex = stack[-1]

        if graph[vertex]:
            neighbor = graph[vertex].pop()
            graph[neighbor].remove(vertex)
            stack.append(neighbor)
        else:
            path.append(stack.pop())

    path.reverse()

    return path

Example:

graph = {
    "A": ["B", "D"],
    "B": ["A", "C"],
    "C": ["B", "D"],
    "D": ["A", "C"],
}

print(euler_path_undirected(graph))

Possible output:

['A', 'D', 'C', 'B', 'A']

Why Backtracking Builds the Path

The algorithm walks edges until it reaches a vertex with no unused outgoing edges.

At that point, the vertex must be final within the current partial route.

So it is appended to the answer.

Backtracking continues, appending vertices only when no more unused edges remain.

This postorder behavior ensures that cycles are stitched together correctly.

The final reverse produces the Euler traversal.

Directed Euler Conditions

For directed graphs, use in-degree and out-degree.

An Euler circuit exists if:

in_degree(v) == out_degree(v)

for every vertex, and all non-isolated vertices lie in one strongly connected region when directions are respected appropriately.

An Euler path exists if:

Vertex Type Degree Condition
Start vertex out-degree = in-degree + 1
End vertex in-degree = out-degree + 1
All others in-degree = out-degree

All other cases fail.

Recipe: Directed Degree Check

def directed_degrees(graph):
    indegree = {
        vertex: 0
        for vertex in graph
    }

    outdegree = {
        vertex: len(neighbors)
        for vertex, neighbors in graph.items()
    }

    for source, neighbors in graph.items():
        for target in neighbors:
            indegree[target] += 1

    return indegree, outdegree

Then:

def euler_type_directed(graph):
    indegree, outdegree = directed_degrees(graph)

    starts = 0
    ends = 0

    for vertex in graph:
        diff = outdegree[vertex] - indegree[vertex]

        if diff == 1:
            starts += 1
        elif diff == -1:
            ends += 1
        elif diff != 0:
            return "none"

    if starts == 0 and ends == 0:
        return "circuit"

    if starts == 1 and ends == 1:
        return "path"

    return "none"

This captures the degree condition for directed Euler traversal.

Applications

Route Inspection

A city wants to inspect every street segment exactly once where possible.

Edges are streets.

Vertices are intersections.

Euler paths model the desired route.

Drawing Problems

The classic question:

Can this figure be drawn without lifting the pen and without retracing a line?

is an Euler path problem.

Genome Assembly

Some genome assembly algorithms model fragments as edges in a de Bruijn graph.

Finding a sequence can become an Euler path problem.

Network Testing

A diagnostic tool may need to traverse every link.

Euler traversal gives the ideal case when it exists.

Complexity Analysis

Let:

  • V = number of vertices
  • E = number of edges

For adjacency-list graphs:

Operation Complexity
Degree check O(V + E)
Connectivity check O(V + E)
Hierholzer traversal O(V + E) with efficient edge removal
Memory usage O(V + E)

The simple Python implementation using list.remove can degrade because removal from a list is linear.

For large graphs, store edge IDs or use multisets to avoid this overhead.

Common Pitfalls

Do not confuse Euler paths with Hamiltonian paths.

Euler paths use every edge exactly once.

Hamiltonian paths visit every vertex exactly once.

Do not check only degree conditions and ignore connectivity.

Do not forget that isolated vertices do not prevent Euler traversal.

Do not use slow edge removal on large graphs.

Do not assume the Euler path is unique.

Many graphs have multiple valid Euler paths.

Do not ignore parallel edges. Euler algorithms must treat each edge occurrence separately.

Takeaway

Euler paths traverse every edge exactly once. In undirected graphs, their existence is determined by connectivity and the number of odd-degree vertices. In directed graphs, in-degree and out-degree determine the possible start and end vertices. Hierholzer's algorithm constructs the traversal efficiently and forms the standard practical method for Euler path and Euler circuit problems.