PK

PKBytes

Explore tracks
Chapter 41: Advanced Graph Structure and Specialized Graph Problems
41.01Intermediate / Advanced4 topics17 min2 interactive animations

Eulerian paths/circuits

An Euler trail uses every edge exactly once. Whether one exists is decided by degrees (or in/out balance) and connectivity alone, and Hierholzer's algorithm builds the trail in linear time.

Learning goals

  • State the degree and balance conditions for Euler trails and circuits
  • Explain why connectivity of the edges is also required
  • Run Hierholzer's algorithm with a stack
  • Tell Euler trails apart from Hamiltonian paths

Prerequisites

Graph representations and DFS (Chapters 32-33)Connected components

Can you cross every bridge of a town exactly once? Euler asked this in 1736 and founded graph theory by answering it. The same question appears in snow-plough routes, DNA fragment assembly and plotter drawing, and unlike its look-alike, the Hamiltonian path, it has a fast exact answer.

41.01.1

Degree conditions

An **Euler trail** walks along every edge exactly once; an **Euler circuit** does the same and returns to its start. Each time a trail passes through a vertex it uses two of its edges, one to arrive and one to leave. So every vertex in the middle of the trail has even degree. Only the two ends of an open trail can have odd degree, because the first edge out of the start and the last edge into the end are unpaired. Euler's own puzzle, the seven bridges of Königsberg, has four land masses of degrees 5, 3, 3 and 3: four odd vertices, so no walk crosses every bridge exactly once.

This gives the **degree condition** for an undirected graph: a circuit needs every degree even, and an open trail needs exactly two odd vertices, which are its ends. Any other number of odd vertices is impossible; by the handshake lemma the count of odd vertices is always even, so the only cases are 0, 2 or at least 4.

Open the animation. The first preset has two triangles sharing vertex 2: all degrees are even, so a circuit exists. The path preset has odd vertices 0 and 1, so the trail must start at one of them and end at the other. The “four odd vertices” preset (a star with three leaves) is rejected before any searching; the answer is decided from the degrees alone in O(V + E).

Java
1// returns "circuit", "path" or "none" using only the degree condition (connectivity is checked separately)
2static String eulerKindByDegree(int n, int[][] edges) {
3    int[] degree = new int[n];
4    for (int[] e : edges) { degree[e[0]]++; degree[e[1]]++; }
5    int odd = 0;
6    for (int d : degree) if (d % 2 == 1) odd++;                       // the handshake lemma makes this number even
7    return odd == 0 ? "circuit" : odd == 2 ? "path" : "none";
8}

Euler trails and circuits: degree conditions and Hierholzer's algorithm

Interactive · edit the input

Your input

Try

undirected graph · 5 vertices · 6 edges

0

deg 2

1

deg 2

2

deg 4

3

deg 2

4

deg 2

Top of the stack / edge just takenOn the stackEdge used or vertex in the trail

degree of each vertex

20
21
42
23
24

stack (top on the right)

empty

trail built so far (front first)

empty
Setup

An Euler trail uses every edge exactly once. The degree of each vertex is shown: a circuit needs every degree even; a trail needs exactly two odd vertices (the ends).

Step 1 / 17
Java
1// edges {a, b}; returns the vertices of a trail that uses every edge exactly once, or null when none exists
2@SuppressWarnings("unchecked")
3static List<Integer> eulerTrail(int n, int[][] edges, boolean directed) {
4    List<int[]>[] adj = new List[n];                                  // arc {neighbour, edge id}
5    int[] balance = new int[n];                                       // directed: out - in; undirected: degree
6    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
7    for (int id = 0; id < edges.length; id++) {
8        int a = edges[id][0], b = edges[id][1];
9        adj[a].add(new int[]{b, id});
10        if (directed) { balance[a]++; balance[b]--; }
11        else { adj[b].add(new int[]{a, id}); balance[a]++; balance[b]++; }
12    }
13    int start = -1, plus = 0, minus = 0, odd = 0;
14    for (int v = 0; v < n; v++) {                                     // 1. degree / balance conditions
15        if (directed) {
16            if (balance[v] == 1) { plus++; start = v; }               // one vertex may have one more edge out than in
17            else if (balance[v] == -1) minus++;                       // and one may have one more in than out
18            else if (balance[v] != 0) return null;
19        } else if (balance[v] % 2 == 1) {
20            odd++;
21            if (start == -1) start = v;                               // a trail must start at an odd vertex
22        }
23    }
24    if (directed ? plus != minus || plus > 1 : odd != 0 && odd != 2) return null;
25    if (start == -1) start = edges[0][0];                             // all balanced: a circuit may start anywhere
26    boolean[] used = new boolean[edges.length];
27    int[] next = new int[n];                                          // next unexplored arc of each vertex
28    Deque<Integer> stack = new ArrayDeque<>(List.of(start));
29    LinkedList<Integer> trail = new LinkedList<>();
30    while (!stack.isEmpty()) {                                        // 2. Hierholzer
31        int v = stack.peek();
32        while (next[v] < adj[v].size() && used[adj[v].get(next[v])[1]]) next[v]++;   // skip edges used from the other end
33        if (next[v] == adj[v].size()) { trail.addFirst(v); stack.pop(); }             // stuck: v is final in the trail
34        else {
35            int[] arc = adj[v].get(next[v]++);
36            used[arc[1]] = true;
37            stack.push(arc[0]);
38        }
39    }
40    return trail.size() == edges.length + 1 ? trail : null;           // too short: some edges are in another component
41}

Live state

0 edges used0 dead ends

n

5

edges

6

kind

undirected

No condition evaluated on this step
Execution trace (dry run table)Show 17 steps
StepLineStateWhat happens
1L3n=5 edges=6 kind=undirectedAn Euler trail uses every edge exactly once. The degree of each vertex is shown: a circuit needs every degree even; a trail needs exactly two odd vertices (the ends).
2L24start=0 kind=circuitEvery vertex is balanced, so a circuit can start anywhere; start at 0. Connectivity is still unchecked; Hierholzer's algorithm will reveal it.
3L28start=0Hierholzer: walk along unused edges until stuck, pushing vertices on a stack. A stuck vertex is final, so it moves to the front of the trail; then go back and splice in the detours.
4L37from=0 to=1 edge=0Take the unused edge 0-1 and move to 1.
5L37from=1 to=2 edge=1Take the unused edge 1-2 and move to 2.
6L37from=2 to=0 edge=2Take the unused edge 2-0 and move to 0.
7L33stuck=0 trail=0Vertex 0 has no unused edge left: it is final, so it goes to the front of the trail. Back up to 2.
8L37from=2 to=3 edge=3Take the unused edge 2-3 and move to 3.
9L37from=3 to=4 edge=4Take the unused edge 3-4 and move to 4.
10L37from=4 to=2 edge=5Take the unused edge 4-2 and move to 2.
11L33stuck=2 trail=2→0Vertex 2 has no unused edge left: it is final, so it goes to the front of the trail. Back up to 4.
12L33stuck=4 trail=4→2→0Vertex 4 has no unused edge left: it is final, so it goes to the front of the trail. Back up to 3.
13L33stuck=3 trail=3→4→2→0Vertex 3 has no unused edge left: it is final, so it goes to the front of the trail. Back up to 2.
14L33stuck=2 trail=2→3→4→2→0Vertex 2 has no unused edge left: it is final, so it goes to the front of the trail. Back up to 1.
15L33stuck=1 trail=1→2→3→4→2→0Vertex 1 has no unused edge left: it is final, so it goes to the front of the trail. Back up to 0.
16L33stuck=0 trail=0→1→2→3→4→2→0Vertex 0 has no unused edge left: it is final, so it goes to the front of the trail.
17L40return=0→1→2→3→4→2→0 edges=6Euler circuit: 0→1→2→3→4→2→0. All 6 edges are used exactly once.
41.01.2

Directed balance

In a directed graph a trail enters a vertex along one arc and leaves along another, so in the middle of a trail the number of arcs in equals the number of arcs out. Define the **balance** of a vertex as out-degree minus in-degree. For an **Euler circuit** every balance must be 0. For an open **Euler trail** exactly one vertex may have balance +1 (the start: it has one more arc out than in) and exactly one may have −1 (the end).

The check is again a single pass over the arcs. Note the asymmetry with the undirected case: the parity of a degree is not enough, because arcs have a direction, and a vertex with two arcs out and none in has even degree but balance +2 and kills any trail.

Try the animation with the directed presets. “Directed circuit” has all balances 0 and the trail 0→1→2→3→1→3→0 returns to its start. In “Directed trail” vertex 2 has two arcs out and one in (balance +1) and vertex 3 has one in and none out (balance −1), so the trail must start at 2 and end at 3: it is found as 2→0→1→2→3.

GraphEuler circuitEuler trail (open)
Undirectedevery degree evenexactly two odd vertices (the ends)
Directedout = in at every vertexone vertex with out − in = +1 (start), one with −1 (end), the rest 0
Bothall edges in one connected componentall edges in one connected component
Java
1// arcs {from, to}; the balance condition only (connectivity is checked separately)
2static String eulerKindDirected(int n, int[][] arcs) {
3    int[] balance = new int[n];                                       // out-degree minus in-degree
4    for (int[] a : arcs) { balance[a[0]]++; balance[a[1]]--; }
5    int plus = 0, minus = 0;
6    for (int b : balance) {
7        if (b == 1) plus++;
8        else if (b == -1) minus++;
9        else if (b != 0) return "none";                               // any larger imbalance rules a trail out
10    }
11    if (plus == 0 && minus == 0) return "circuit";
12    return plus == 1 && minus == 1 ? "path" : "none";
13}
41.01.3

Connectivity conditions

The degree or balance condition only talks about single vertices. A trail is one connected walk, so **all edges must lie in one connected component**. Isolated vertices (with no edges) are irrelevant and may be ignored, but two cycles that never touch cannot be walked as one trail, however even their degrees are.

For undirected graphs, connectivity of the edges together with the degree condition is both necessary and sufficient. For directed graphs, **weak** connectivity (ignoring arc directions) plus the balance condition is also enough: if every vertex is balanced and the arcs are weakly connected, the graph is automatically strongly connected on its non-isolated vertices, so a circuit exists. You do not need to test strong connectivity separately.

The check below uses a union-find structure: merge the two ends of every edge, then confirm all edges share one root. The animation's disconnected preset shows the failure mode: the degrees are all even, but Hierholzer's walk uses only 3 of the 6 edges and reports that the rest lie in another component.

Java
1// true when every edge lies in one connected component (isolated vertices do not matter)
2static boolean edgesConnected(int n, int[][] edges) {
3    int[] parent = new int[n];
4    for (int i = 0; i < n; i++) parent[i] = i;
5    for (int[] e : edges) parent[find(parent, e[0])] = find(parent, e[1]);
6    int root = -1;
7    for (int[] e : edges) {
8        int r = find(parent, e[0]);
9        if (root == -1) root = r;
10        else if (r != root) return false;
11    }
12    return true;
13}
14static int find(int[] parent, int x) {
15    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
16    return x;
17}
41.01.4

Hierholzer's algorithm

**Hierholzer's algorithm** builds the trail in O(V + E). Keep a stack with the start vertex. Repeatedly look at the vertex on top: if it still has an unused edge, take it, mark it used, and push the new vertex; if it has none, pop it and put it at the **front** of the trail. A vertex is popped exactly when it is stuck, and the first stuck vertex is the end of the trail (in a circuit, the start again).

The idea is that walking along unused edges from a vertex in a graph with all-even degrees can only get stuck back at the start, so the walk makes a closed loop. The vertices where unused edges remain are detours that are spliced in later, in the right place, because they are put at the front of the trail when they are finally finished. An open trail must start at the odd vertex; otherwise the walk could close too early.

In the code, next[v] is a pointer into the adjacency list so that every arc is looked at only once, and used[] marks an undirected edge as used from both ends. In the animation's first preset the trail grows backwards as vertices are popped: the stack shows the walk in progress, and the trail row shows the finished tail. The result 0→1→2→3→4→2→0 uses all 6 edges.

Java
1// edges {a, b}; returns the vertices of a trail that uses every edge exactly once, or null when none exists
2@SuppressWarnings("unchecked")
3static List<Integer> eulerTrail(int n, int[][] edges, boolean directed) {
4    List<int[]>[] adj = new List[n];                                  // arc {neighbour, edge id}
5    int[] balance = new int[n];                                       // directed: out - in; undirected: degree
6    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
7    for (int id = 0; id < edges.length; id++) {
8        int a = edges[id][0], b = edges[id][1];
9        adj[a].add(new int[]{b, id});
10        if (directed) { balance[a]++; balance[b]--; }
11        else { adj[b].add(new int[]{a, id}); balance[a]++; balance[b]++; }
12    }
13    int start = -1, plus = 0, minus = 0, odd = 0;
14    for (int v = 0; v < n; v++) {                                     // 1. degree / balance conditions
15        if (directed) {
16            if (balance[v] == 1) { plus++; start = v; }               // one vertex may have one more edge out than in
17            else if (balance[v] == -1) minus++;                       // and one may have one more in than out
18            else if (balance[v] != 0) return null;
19        } else if (balance[v] % 2 == 1) {
20            odd++;
21            if (start == -1) start = v;                               // a trail must start at an odd vertex
22        }
23    }
24    if (directed ? plus != minus || plus > 1 : odd != 0 && odd != 2) return null;
25    if (start == -1) start = edges[0][0];                             // all balanced: a circuit may start anywhere
26    boolean[] used = new boolean[edges.length];
27    int[] next = new int[n];                                          // next unexplored arc of each vertex
28    Deque<Integer> stack = new ArrayDeque<>(List.of(start));
29    LinkedList<Integer> trail = new LinkedList<>();
30    while (!stack.isEmpty()) {                                        // 2. Hierholzer
31        int v = stack.peek();
32        while (next[v] < adj[v].size() && used[adj[v].get(next[v])[1]]) next[v]++;   // skip edges used from the other end
33        if (next[v] == adj[v].size()) { trail.addFirst(v); stack.pop(); }             // stuck: v is final in the trail
34        else {
35            int[] arc = adj[v].get(next[v]++);
36            used[arc[1]] = true;
37            stack.push(arc[0]);
38        }
39    }
40    return trail.size() == edges.length + 1 ? trail : null;           // too short: some edges are in another component
41}

Worst

O(V + E)

Space

O(V + E)

Euler trails and circuits: degree conditions and Hierholzer's algorithm

Interactive · edit the input

Your input

Try

undirected graph · 5 vertices · 6 edges

0

deg 2

1

deg 2

2

deg 4

3

deg 2

4

deg 2

Top of the stack / edge just takenOn the stackEdge used or vertex in the trail

degree of each vertex

20
21
42
23
24

stack (top on the right)

empty

trail built so far (front first)

empty
Setup

An Euler trail uses every edge exactly once. The degree of each vertex is shown: a circuit needs every degree even; a trail needs exactly two odd vertices (the ends).

Step 1 / 17
Java
1// edges {a, b}; returns the vertices of a trail that uses every edge exactly once, or null when none exists
2@SuppressWarnings("unchecked")
3static List<Integer> eulerTrail(int n, int[][] edges, boolean directed) {
4    List<int[]>[] adj = new List[n];                                  // arc {neighbour, edge id}
5    int[] balance = new int[n];                                       // directed: out - in; undirected: degree
6    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
7    for (int id = 0; id < edges.length; id++) {
8        int a = edges[id][0], b = edges[id][1];
9        adj[a].add(new int[]{b, id});
10        if (directed) { balance[a]++; balance[b]--; }
11        else { adj[b].add(new int[]{a, id}); balance[a]++; balance[b]++; }
12    }
13    int start = -1, plus = 0, minus = 0, odd = 0;
14    for (int v = 0; v < n; v++) {                                     // 1. degree / balance conditions
15        if (directed) {
16            if (balance[v] == 1) { plus++; start = v; }               // one vertex may have one more edge out than in
17            else if (balance[v] == -1) minus++;                       // and one may have one more in than out
18            else if (balance[v] != 0) return null;
19        } else if (balance[v] % 2 == 1) {
20            odd++;
21            if (start == -1) start = v;                               // a trail must start at an odd vertex
22        }
23    }
24    if (directed ? plus != minus || plus > 1 : odd != 0 && odd != 2) return null;
25    if (start == -1) start = edges[0][0];                             // all balanced: a circuit may start anywhere
26    boolean[] used = new boolean[edges.length];
27    int[] next = new int[n];                                          // next unexplored arc of each vertex
28    Deque<Integer> stack = new ArrayDeque<>(List.of(start));
29    LinkedList<Integer> trail = new LinkedList<>();
30    while (!stack.isEmpty()) {                                        // 2. Hierholzer
31        int v = stack.peek();
32        while (next[v] < adj[v].size() && used[adj[v].get(next[v])[1]]) next[v]++;   // skip edges used from the other end
33        if (next[v] == adj[v].size()) { trail.addFirst(v); stack.pop(); }             // stuck: v is final in the trail
34        else {
35            int[] arc = adj[v].get(next[v]++);
36            used[arc[1]] = true;
37            stack.push(arc[0]);
38        }
39    }
40    return trail.size() == edges.length + 1 ? trail : null;           // too short: some edges are in another component
41}

Live state

0 edges used0 dead ends

n

5

edges

6

kind

undirected

No condition evaluated on this step
Execution trace (dry run table)Show 17 steps
StepLineStateWhat happens
1L3n=5 edges=6 kind=undirectedAn Euler trail uses every edge exactly once. The degree of each vertex is shown: a circuit needs every degree even; a trail needs exactly two odd vertices (the ends).
2L24start=0 kind=circuitEvery vertex is balanced, so a circuit can start anywhere; start at 0. Connectivity is still unchecked; Hierholzer's algorithm will reveal it.
3L28start=0Hierholzer: walk along unused edges until stuck, pushing vertices on a stack. A stuck vertex is final, so it moves to the front of the trail; then go back and splice in the detours.
4L37from=0 to=1 edge=0Take the unused edge 0-1 and move to 1.
5L37from=1 to=2 edge=1Take the unused edge 1-2 and move to 2.
6L37from=2 to=0 edge=2Take the unused edge 2-0 and move to 0.
7L33stuck=0 trail=0Vertex 0 has no unused edge left: it is final, so it goes to the front of the trail. Back up to 2.
8L37from=2 to=3 edge=3Take the unused edge 2-3 and move to 3.
9L37from=3 to=4 edge=4Take the unused edge 3-4 and move to 4.
10L37from=4 to=2 edge=5Take the unused edge 4-2 and move to 2.
11L33stuck=2 trail=2→0Vertex 2 has no unused edge left: it is final, so it goes to the front of the trail. Back up to 4.
12L33stuck=4 trail=4→2→0Vertex 4 has no unused edge left: it is final, so it goes to the front of the trail. Back up to 3.
13L33stuck=3 trail=3→4→2→0Vertex 3 has no unused edge left: it is final, so it goes to the front of the trail. Back up to 2.
14L33stuck=2 trail=2→3→4→2→0Vertex 2 has no unused edge left: it is final, so it goes to the front of the trail. Back up to 1.
15L33stuck=1 trail=1→2→3→4→2→0Vertex 1 has no unused edge left: it is final, so it goes to the front of the trail. Back up to 0.
16L33stuck=0 trail=0→1→2→3→4→2→0Vertex 0 has no unused edge left: it is final, so it goes to the front of the trail.
17L40return=0→1→2→3→4→2→0 edges=6Euler circuit: 0→1→2→3→4→2→0. All 6 edges are used exactly once.

Practice ladder

Now try it yourself

Easy

  • Find the Town Judge

Medium

  • Reconstruct Itinerary

Advanced

  • Cracking the Safe
  • Valid Arrangement of Pairs

Key takeaways

  • Euler circuit: all degrees even (undirected) or all balances 0 (directed); Euler trail: two odd vertices, or one +1 and one −1.
  • All edges must lie in one connected component.
  • Hierholzer: walk until stuck, finish stuck vertices to the front of the trail, splice detours back in; O(V + E).