Eulerian Path and Circuit

Eulerian Path and Circuit is the classic "draw this shape without lifting your pen" puzzle, turned into a graph problem. The whole thing hinges on a single, beautiful counting rule about vertex degrees.

The slow way first

The brute-force instinct is to try every possible ordering of edges and check whether one forms a valid single-pass walk. With m edges that is up to m! orderings — hopeless for anything but a tiny graph.

The question to ask: is there a cheap structural test that tells me whether such a walk can exist at all, before I try to build one? There is, and it depends only on the degree of each vertex.

The idea: count odd degrees

Every time a walk passes through a vertex, it uses one edge to enter and one to leave — edges get consumed in pairs. So a vertex you pass through must have an even degree. The only vertices allowed to have an odd degree are the two endpoints of the walk (you leave the start without entering, and enter the end without leaving).

That gives the rule for a connected graph:

Zero odd vertices → Euler circuit. Exactly two → Euler path starting at one odd vertex and ending at the other. Any other count (only 1, or 4, or more) → no Euler trail. Once the test passes, you build the actual walk with Hierholzer's algorithm, greedily following unused edges and splicing in detours.

Walk through it

Step through the animation. First each vertex gets a deg= label. Then the two odd-degree vertices (B and C) light up red — exactly two, so an Euler path exists. Finally the walk traces edge by edge, each one turning green as it is used, starting at B and ending at C.

Pseudocode

count degree[v] for every vertex
odd = vertices whose degree is odd
if number of odd vertices is not 0 and not 2:
    return "no Euler trail"
start = an odd vertex if any, else any vertex
# Hierholzer: greedily follow unused edges, backtrack to emit
push start onto a stack
while stack not empty:
    v = top of stack
    if v still has an unused edge (v, w):
        mark that edge used; push w
    else:
        pop v into the trail
trail reversed is the Euler walk

The Python solution

def euler_trail(n, edges):
    deg = [0] * n
    for u, v in edges:        # tally every endpoint
        deg[u] += 1
        deg[v] += 1
    odd = [v for v in range(n) if deg[v] % 2 == 1]
    if len(odd) not in (0, 2):
        return None           # no Euler trail
    start = odd[0] if odd else 0
    trail = []
    stack = [start]
    while stack:              # Hierholzer's algorithm
        v = stack[-1]
        if adj[v]:
            stack.append(take_edge(v))
        else:
            trail.append(stack.pop())
    return trail[::-1]

• deg counts how many edges touch each vertex; every edge bumps both of its endpoints.
• odd collects the vertices with an odd degree — the only ones allowed to be trail endpoints.
• The len(odd) not in (0, 2) check is the whole decision: 0 means circuit, 2 means path, anything else means impossible.
• start must be an odd vertex when there are two, so the path begins at a valid endpoint; for a circuit any vertex works.
• The while stack loop is Hierholzer's algorithm: follow unused edges as deep as you can, and when a vertex is stuck, pop it into the trail. Reversing the popped order gives the walk.

Complexity

The degree rule replaces an astronomical search with a single linear pass, and constructing the actual walk is linear too.

When this pattern shows up

Practice