What is an Eulerian Path and Eulerian Circuit?
Learn Eulerian paths and circuits, the degree-parity rule, Hierholzer's algorithm, and how to answer this graph interview question.
Expected Interview Answer
An Eulerian path is a walk through a graph that uses every edge exactly once, and an Eulerian circuit is an Eulerian path that starts and ends at the same vertex; an undirected connected graph has a circuit if and only if every vertex has even degree, and a path (not a circuit) if and only if exactly zero or two vertices have odd degree.
The degree condition comes from a simple counting argument: every time the walk passes through a vertex, it uses one edge to enter and one to leave, consuming two of that vertex's edges, so any vertex you don't start or end at must have even degree to be fully consumed. The two exceptions are the start and end vertices, which can have odd degree since the walk only enters or only leaves them once unmatched. For directed graphs the equivalent condition is that every vertex's in-degree equals its out-degree for a circuit, or exactly one vertex has out-degree minus in-degree equal to 1 (the start) and one has in-degree minus out-degree equal to 1 (the end) for a path. Hierholzer's algorithm constructs the actual circuit or path in O(E) time by repeatedly finding and splicing in cycles, which is more efficient than the exponential brute-force approach of trying edge orderings directly. This differs fundamentally from a Hamiltonian path, which visits every vertex once and has no known polynomial-time solution.
- Degree-parity check verifies existence in O(V + E), no search needed
- Hierholzer's algorithm constructs the actual path in linear O(E) time
- Directly models real problems: route inspection, DNA fragment assembly
- Clear contrast with the NP-hard Hamiltonian path problem
AI Mentor Explanation
An Eulerian circuit is like a groundsman needing to walk every boundary rope segment around the ground exactly once and return to the pavilion gate where they started. This is only possible if every marker post along the boundary connects an even number of rope segments, since the groundsman must enter and leave each post the same number of times. If instead exactly two posts have an odd number of segments, an Eulerian path still exists, but the groundsman must start at one odd post and finish at the other, never returning to the gate. This is a completely different puzzle from visiting every marker post exactly once (a Hamiltonian-style walk), which has no known fast solution.
Step-by-Step Explanation
Step 1
Check connectivity
All vertices with non-zero degree must belong to a single connected component; otherwise no Eulerian walk exists.
Step 2
Count vertices with odd degree
For undirected graphs: 0 odd-degree vertices means a circuit exists; exactly 2 means a path exists; any other count means neither exists.
Step 3
Pick the start vertex
For a circuit, start anywhere; for a path, start at one of the two odd-degree vertices.
Step 4
Construct the walk with Hierholzer's algorithm
Follow unused edges until stuck, splice in any detected sub-cycles at their junction vertices, repeat until all edges are used.
What Interviewer Expects
- State the exact degree-parity conditions for circuit vs path
- Explain the counting argument for why the condition holds
- Name Hierholzer's algorithm and its O(E) complexity
- Distinguish Eulerian (edge-covering) from Hamiltonian (vertex-covering) clearly
Common Mistakes
- Confusing Eulerian path/circuit (uses every edge once) with Hamiltonian path/circuit (visits every vertex once)
- Forgetting the connectivity precondition before checking vertex degrees
- Applying the undirected odd-degree rule directly to a directed graph without adjusting for in/out-degree
- Assuming brute-force search is required instead of the linear-time degree check
Best Answer (HR Friendly)
“An Eulerian path uses every single edge in a graph exactly once, and an Eulerian circuit does the same but ends where it started. I check for it just by counting how many vertices have an odd number of connections — zero means a circuit exists, exactly two means a path exists, and I'd use Hierholzer's algorithm to actually build the route.”
Code Example
from collections import defaultdict
def has_eulerian(graph, num_vertices):
odd_degree_vertices = [v for v in range(num_vertices) if len(graph.get(v, [])) % 2 == 1]
if len(odd_degree_vertices) == 0:
return "circuit"
if len(odd_degree_vertices) == 2:
return "path"
return "none"
def hierholzer(graph, start):
adj = {u: list(neighbors) for u, neighbors in graph.items()}
stack = [start]
circuit = []
while stack:
vertex = stack[-1]
if adj.get(vertex):
next_vertex = adj[vertex].pop()
adj[next_vertex].remove(vertex)
stack.append(next_vertex)
else:
circuit.append(stack.pop())
return circuit[::-1]Follow-up Questions
- How does the degree condition change for directed graphs?
- Walk through why Hierholzer's algorithm runs in O(E) time.
- How is the Eulerian path problem different from the Traveling Salesman / Hamiltonian path problem in terms of complexity?
- How would you solve the classic "route inspection" (Chinese Postman) problem when the graph has more than two odd-degree vertices?
MCQ Practice
1. A connected undirected graph has an Eulerian circuit if and only if:
Even degree at every vertex ensures the walk can enter and leave each vertex an equal number of times, closing the loop.
2. How many vertices must have odd degree for a connected undirected graph to have an Eulerian path but not a circuit?
Exactly two odd-degree vertices allow a path that starts at one and ends at the other, but cannot close into a circuit.
3. What is the key difference between an Eulerian path and a Hamiltonian path?
Eulerian paths are edge-covering walks with an efficient degree-based test; Hamiltonian paths are vertex-covering and NP-hard in general.
Flash Cards
What is an Eulerian path? — A walk that uses every edge in the graph exactly once.
What is an Eulerian circuit? — An Eulerian path that starts and ends at the same vertex.
What condition guarantees an Eulerian circuit in a connected undirected graph? — Every vertex has even degree.
What algorithm constructs an Eulerian path/circuit in O(E) time? — Hierholzer's algorithm, which splices in sub-cycles as it walks unused edges.