6.4 Euler Circuits and the Chinese Postman Problem

In the first section, we created a graph of the Königsberg bridges and asked whether it was possible to walk across every bridge once. Because Euler first studied this question, these types of paths are named after him.

Example 1

In the graph shown below, there are several Euler paths.

Adjacency Table

Adjacency table
	A	B	C	D
A	*	1	1
B	1	*	1	1
C	1	1	*	1
D		1	1	*

Show solution

One such path is CABDCB. The path is shown in arrows to the right, with the order of edges numbered.

Example 2

The graph below has several possible Euler circuits.

Adjacency Table

Adjacency table
	A	B	C	D	E	F
A	*	1	1	1	1
B	1	*	1
C	1	1	*		1	1
D	1			*	1
E	1		1	1	*	1
F			1		1	*

Show solution

Here’s a couple, starting and ending at vertex A: ADEACEFCBA and AECABCFEDA. The second is shown in arrows.

Look back at the example used for Euler paths – does that graph have an Euler circuit? A few tries will tell you no; that graph does not have an Euler circuit. When we were working with shortest paths, we were interested in the optimal path. With Euler paths and circuits, we’re primarily interested in whether an Euler path or circuit exists.

Why do we care if an Euler circuit exists? Think back to our housing development lawn inspector from the beginning of the chapter. The lawn inspector is interested in walking as little as possible. The ideal situation would be a circuit that covers every street with no repeats. That’s an Euler circuit! Luckily, Euler solved the question of whether or not an Euler path or circuit will exist.

Note

Euler’s Path and Circuit Theorems

A graph will contain an Euler path if it contains at most two vertices of odd degree.

A graph will contain an Euler circuit if all vertices have even degree

# Ch 6.4 - Euler's theorems decide IF a circuit exists; Fleury's algorithm FINDS one.
EDGES = [("A", "C"), ("A", "D"), ("B", "D"), ("B", "E"), ("C", "D"), ("D", "E")]
# TRY IT: delete ("D","E") and re-run - two vertices go odd and the circuit dies.
# TRY IT: add ("A","B") as well and re-run - now four vertices are odd.

def build(edges):
    g = {}
    for u, v in edges:
        g.setdefault(u, []).append(v)
        g.setdefault(v, []).append(u)
    return g

G = build(EDGES)
odd = [v for v in sorted(G) if len(G[v]) % 2]
for v in sorted(G):
    print(f"   degree({v}) = {len(G[v])}" + ("   <- odd" if v in odd else ""))
verdict = ("every degree is even -> an Euler CIRCUIT exists" if not odd else
           f"an Euler PATH exists, starting at {odd[0]} and ending at {odd[1]},"
           " but no Euler circuit" if len(odd) == 2 else
           "more than two odd vertices -> no Euler path and no Euler circuit")
print(f"\n{len(odd)} vertices have odd degree, so Euler says:\n   {verdict}")

def reachable_from(edges, src):
    g, seen, stack = build(edges), set(), [src]
    while stack:
        v = stack.pop()
        if v not in seen:
            seen.add(v)
            stack += g.get(v, [])
    return seen

def fleury(edges, start):
    remaining, route, cur = list(edges), [start], start
    while remaining:
        here = sorted(e for e in remaining if cur in e)
        pick = None
        for e in here:
            other = e[0] if e[1] == cur else e[1]
            rest = [x for x in remaining if x != e]
            if not rest or other in reachable_from(rest, cur):
                pick = e            # not a bridge: we can still get back
                break
        if pick is None:
            pick = here[0]          # forced to cross a bridge
        cur = pick[0] if pick[1] == cur else pick[1]
        remaining.remove(pick)
        route.append(cur)
    return route

if len(odd) in (0, 2):
    start = odd[0] if odd else sorted(G)[0]
    route = fleury(EDGES, start)
    kind = "circuit" if not odd else "path"
    print(f"\nFleury starting at {start}: {''.join(route)}"
          f"   ({len(route) - 1} moves for {len(EDGES)} edges)")
    print(f"written backwards it is {''.join(reversed(route))} - the same {kind},"
          " which is why the book's answer can look different from yours")
    used = sorted(tuple(sorted(e)) for e in zip(route, route[1:]))
    print(f"every edge used exactly once? {used == sorted(tuple(sorted(e)) for e in EDGES)}")
else:
    print("\nnothing for Fleury to find - some edge would have to be repeated.")

Example 3

In the graph below, vertices A and C have degree 4, since there are 4 edges leading into each vertex. B is degree 2, D is degree 3, and E is degree 1. This graph contains two vertices with odd degree (D and E) and three vertices with even degree (A, B, and C), so Euler’s theorems tell us this graph has an Euler path, but not an Euler circuit.

Adjacency Table

Adjacency table, with values showing the number of edges connecting each pair
	A	B	C	D	E
A	*	1	2	1
B	1	*		1
C	2		*	1	1
D	1	1	1	*
E			1		*

Now we know how to determine if a graph has an Euler circuit, but if it does, how do we find one? While it usually is possible to find an Euler circuit just by pulling out your pencil and trying to find one, the more formal method is Fleury’s algorithm.

Example 6

Let’s find an Euler Circuit on this graph using Fleury’s algorithm, starting at vertex A.

Show solution

Step 1:

Original Graph. Choosing edge AD.

Adjacency Table

Adjacency table
	A	B	C	D	E
A	*		1	1
B		*		1	1
C	1		*	1
D	1	1	1	*	1
E		1		1	*

Circuit so far: AD

Step 2:

AD deleted. D is current. Can’t choose DC since that would disconnect graph. Choosing DE

Adjacency Table

Adjacency table
	A	B	C	D	E
A	*		1	deleted
B		*		1	1
C	1		*	1
D	deleted	1	1	*	1
E		1		1	*

Circuit so far: ADE

Step 3:

E is current. From here, there is only one option, so the rest of the circuit is determined.

Adjacency Table

Adjacency table
	A	B	C	D	E
A	*		1
B		*		1	1
C	1		*	1
D		1	1	*	deleted
E		1		deleted	*

Circuit: ADEBDCA

Your Turn

Try it Now 3

Does the graph below have an Euler Circuit? If so, find one.

Adjacency Table

Adjacency table
	A	B	C	D	E
A	*		1	1
B		*		1	1
C	1		*	1
D	1	1	1	*	1
E		1		1	*

Answer

Yes, all vertices have even degree so this graph has an Euler Circuit. There are several possibilities. One is: ABEGFCDFEDBCA

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.