What Is an Eulerian Path? The Edge-Walk Every Graph Hides

1. Euler had a problem. Not a personal problem. A bridge problem.

The city of Königsberg had seven bridges connecting four landmasses across the Pregel River. The locals wanted to know: could you walk through the city crossing every bridge exactly once? People had been trying and failing for years. It was the kind of puzzle that made you feel dumb at a dinner party.

Euler didn't just answer the question. He invented an entire branch of mathematics to do it. The result was graph theory, and the concept at its center is what we now call an Eulerian path.

An Eulerian path is a path through a graph that visits every edge exactly once. Not every vertex. Every edge. That distinction decides everything, including whether the problem is solvable in polynomial time or NP-complete.

Edges, Not Vertices

The quickest way to confuse yourself is to mix up Eulerian paths with Hamiltonian paths. A Hamiltonian path visits every vertex exactly once. An Eulerian path visits every edge exactly once. Same graph, completely different goal, completely different computational complexity.

Think of it as the difference between visiting every house on a mail route versus walking every street. In the first case, you track houses. In the second, you track streets. You might pass the same house twice, but you never repeat a street.

Eulerian paths are solvable in O(V + E) time. Hamiltonian paths are NP-complete. One condition check decides whether a solution exists. The other has no known polynomial-time characterization and will eat your interview alive if you mix them up.

CS professors when you ask which class of problems you need to know for your interview.

Circuit or Path? One Ends Where It Started.

Two flavors, and keeping them straight matters.

An Eulerian circuit (also called an Eulerian tour) is a closed path that uses every edge exactly once and ends where it started. Start at vertex A, traverse every edge, return to A. Very satisfying. Like folding laundry and having zero leftover socks.

An Eulerian path is the same idea but allowed to start and end at different vertices. Every circuit is a path, but most paths are not circuits.

The difference matters when you check whether a solution exists and which vertex to start from.

The Condition That Decides Everything

Euler's key insight: you don't need to try all possible routes. The answer comes from a single property of each vertex, its degree.

This is the part that should make you feel good about graph theory. No brute force. No exponential blowup. Just count.

Undirected Graphs

For undirected graphs, count the degree of each vertex. The number of odd-degree vertices tells you everything.

• Zero odd-degree vertices: an Eulerian circuit exists.
• Exactly two odd-degree vertices: an Eulerian path exists. Those two vertices are the start and end.
• Any other count: neither exists.

Why does degree parity decide this? Every time you enter a vertex, you leave via a different edge. Edges come in pairs: one in, one out. A vertex with even degree balances perfectly. A vertex with odd degree can only be the start (you leave without entering first) or the end (you enter without leaving last). You can have at most two such exceptions, which is exactly why zero or two odd-degree vertices is the condition.

from collections import defaultdict

def has_eulerian_path(edges: list[list[int]]) -> bool:
    degree = defaultdict(int)
    for u, v in edges:
        degree[u] += 1
        degree[v] += 1
    
    odd_count = sum(1 for d in degree.values() if d % 2 != 0)
    return odd_count == 0 or odd_count == 2

Directed Graphs

For directed graphs, each vertex has an in-degree (edges entering) and an out-degree (edges leaving). The condition shifts from parity to balance.

• Eulerian circuit: every vertex has equal in-degree and out-degree.
• Eulerian path: at most one vertex has out-degree - in-degree = 1 (the start), at most one vertex has in-degree - out-degree = 1 (the end), and every other vertex is balanced.

def has_eulerian_path_directed(edges: list[list[int]]) -> bool:
    in_deg = defaultdict(int)
    out_deg = defaultdict(int)
    
    for u, v in edges:
        out_deg[u] += 1
        in_deg[v] += 1
    
    starts, ends = 0, 0
    for v in set(in_deg) | set(out_deg):
        diff = out_deg[v] - in_deg[v]
        if abs(diff) > 1:
            return False
        if diff == 1:
            starts += 1
        elif diff == -1:
            ends += 1
    
    return (starts == 0 and ends == 0) or (starts == 1 and ends == 1)

For more on in-degree and out-degree as graph concepts, the in-degree and out-degree guide covers the mechanics.

How Euler Proved It Was Impossible

Back to Königsberg. Four landmasses connected by seven bridges. The graph looks like this:

Landmass	Bridges Connected	Degree
A	5	5 (odd)
B	3	3 (odd)
C	3	3 (odd)
D	3	3 (odd)

Four odd-degree vertices. The condition requires zero or two. An Eulerian path is impossible. No route crosses every bridge exactly once. The city had been arguing about it for years and the answer was: stop arguing, it's geometrically impossible.

Euler didn't try every possible route. He noticed the structure. That's what interviews are testing when they ask about this topic.

When Two Odd Vertices Are Enough

Take a simple graph with five edges: A-B, B-C, C-D, D-B, B-E.

Degrees: A has degree 1, B has degree 4, C has degree 2, D has degree 2, E has degree 1. Two odd-degree vertices. A path exists, running from A to E.

One valid route: A → B → C → D → B → E. All five edges used, no repeats. The degree check told you the path existed before you traced a single step.

Hierholzer's Algorithm Finds the Path

Knowing a path exists is half the problem. Finding it is the other half.

Hierholzer's algorithm works in O(V + E) time. The intuition: start at a valid vertex and keep following unvisited edges greedily until you can't move. If the route you've traced doesn't cover all edges, find a vertex in your current route that still has unvisited edges, start a new sub-route from there, and splice it in.

The implementation uses a stack and builds the path in reverse. When you hit a dead end, push that vertex onto the result. Dead ends become the end of the path because you want to reach them last.

from collections import defaultdict

def find_eulerian_path(n: int, edges: list[list[int]]) -> list[int]:
    graph = defaultdict(list)
    in_deg = defaultdict(int)
    out_deg = defaultdict(int)
    
    for u, v in edges:
        graph[u].append(v)
        out_deg[u] += 1
        in_deg[v] += 1
    
    # Start vertex: prefer the one with out-degree - in-degree = 1
    start = edges[0][0]
    for v in set(in_deg) | set(out_deg):
        if out_deg[v] - in_deg[v] == 1:
            start = v
            break
    
    result = []
    stack = [start]
    
    while stack:
        while graph[stack[-1]]:
            next_v = graph[stack[-1]].pop()
            stack.append(next_v)
        result.append(stack.pop())
    
    return result[::-1]

The full algorithm walkthrough, including the proof of correctness and edge cases, is in the Eulerian path algorithm guide.

Why Coding Interviews Use Eulerian Path Problems

Eulerian paths appear in interviews two ways.

Explicitly, as the stated problem. LeetCode 332 (Reconstruct Itinerary) gives you a list of airline tickets and asks you to reconstruct a flight itinerary that uses each ticket exactly once. Each ticket is a directed edge. The destination airport must be visited in lexicographic order when multiple are available. This is a directed Eulerian path: check the in-degree/out-degree balance, then run Hierholzer's with a sorted adjacency list (min-heap) to get lexicographic ordering.

Implicitly, hidden inside a larger problem. LeetCode 753 (Cracking the Safe) asks for the shortest string containing all possible PIN combinations of length n over k digits. Model n-1 digit strings as vertices, and each n-digit sequence as a directed edge. Every vertex has exactly k in-edges and k out-edges, so an Eulerian circuit covers all combinations. The underlying structure is a De Bruijn graph.

The pattern to recognize: "use each connection exactly once" or "visit every edge." Once you see that phrasing, reach for the degree condition check. If it passes, Hierholzer's gives you the path. If you don't recognize it and try to enumerate all possible orderings instead, you're now solving an NP-complete problem under a 45-minute timer.

For a broader look at how DFS underlies Hierholzer's, the depth-first search guide covers the traversal mechanics.

Three Ways to Break It

Skipping the connectivity check. The degree condition is necessary but not sufficient. A graph where two subgraphs are disconnected fails even if every vertex has even degree. Always verify the graph is connected (weakly connected for directed graphs) before claiming a path exists. This is the bug that passes small examples and fails the edge case test at the end of your interview.

Picking the wrong start vertex in directed graphs. The start is the vertex with out-degree - in-degree = 1, not just any odd-degree vertex. If no such vertex exists (all balanced), any vertex works. Wrong start, incomplete path.

Modifying the wrong data structure during traversal. Hierholzer's pops edges as it consumes them. Use a mutable structure per vertex such as an array with a pointer or a deque, not an iterator over a static list. Popping from the wrong end changes the output ordering.

Debugging Hierholzer's when you forgot the connectivity check.

Quick Reference

Graph Type	Eulerian Circuit	Eulerian Path
Undirected	All vertices even degree	Exactly 2 odd-degree vertices
Directed	Every vertex: in == out	One vertex with out-in=1, one with in-out=1

Algorithm: Hierholzer's, O(V + E) time, O(V + E) space.

If you want to drill graph problems under real interview pressure, SpaceComplexity runs voice-based DSA mock interviews and gives rubric-based feedback on your reasoning, not just your final answer. Eulerian path recognition is exactly the kind of pattern-spotting it trains.

Further Reading

• Seven Bridges of Königsberg (Wikipedia)
• Eulerian Path (Wikipedia)
• Eulerian Path and Circuit for Undirected Graph (GeeksforGeeks)
• Hamiltonian Path and Eulerian Path: Differences (GeeksforGeeks)
• LeetCode 332: Reconstruct Itinerary