Unit 21: Every Edge, Every Node

A walk over every bridge, exactly once

A river, two islands, seven bridges. Can you walk a route that crosses every bridge exactly once? Everyone in the town of Königsberg tried; Euler proved it impossible in 1736, and started graph theory doing it.

His argument needs no searching at all.

Count the bridges at each bank

Every time your walk passes through a place it uses two bridges — one in, one out. So a place with an odd number of bridges must be where you start or where you finish.

There are only two ends to a walk. All four places here are odd, so there is no route.

Python

n = 4
bridges = [(0, 1), (0, 1), (0, 2), (0, 2), (0, 3), (1, 3), (2, 3)]

degree = [0] * n
for a, b in bridges:
    degree[a] += 1
    degree[b] += 1

print(degree)
print(sum(1 for d in degree if d % 2 == 1))

It prints

[5, 3, 3, 3]
4

The rule, in full

A connected graph has a walk using every edge once when the number of odd-degree nodes is 0 or 2.

Zero means it comes back to where it started — a circuit. Two means it starts at one odd node and finishes at the other. Anything else is impossible.

Python

def odd_count(n, edges):
    degree = [0] * n
    for a, b in edges:
        degree[a] += 1
        degree[b] += 1
    return sum(1 for d in degree if d % 2 == 1)

print(odd_count(3, [(0, 1), (1, 2), (2, 0)]))
print(odd_count(4, [(0, 1), (1, 2), (2, 3)]))
print(odd_count(4, [(0, 1), (0, 2), (0, 3)]))

It prints

0
2
4

And connected means connected by edges

A node with no edges at all does not spoil anything — there is nothing to walk there. But two separate clumps of edges cannot be joined by a walk, however even the degrees are.

So the check is: at most two odd nodes, and every edge is in one piece.

Knowing one exists is not printing one

The rule says a route exists. A problem wants the route.

Hierholzer's algorithm: keep walking down unused edges until you are stuck, then back up, writing down each node as you get stuck on it. The list, reversed, is the tour.

The stack version

Each node keeps a pointer into its own list of edges, so an edge is never looked at twice and the whole thing is linear.

The two triangles come out as one tour of six edges and seven nodes, ending back at the start.

Python

n = 5
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)]

adj = [[] for i in range(n)]
for index, pair in enumerate(edges):
    a, b = pair
    adj[a].append((b, index))
    adj[b].append((a, index))

used = [False] * len(edges)
pointer = [0] * n
stack = [0]
circuit = []

while stack:
    node = stack[-1]
    while pointer[node] < len(adj[node]) and used[adj[node][pointer[node]][1]]:
        pointer[node] += 1
    if pointer[node] == len(adj[node]):
        circuit.append(stack.pop())
    else:
        nxt, index = adj[node][pointer[node]]
        used[index] = True
        stack.append(nxt)

print(circuit)
print(len(circuit) - 1, len(edges))

It prints

[0, 2, 4, 3, 2, 1, 0]
6 6

Why getting stuck is not a problem

When the walk gets stuck, it can only be back where it started — every other node has an even number of edges, so arriving always leaves a way out.

Anything missed is a loop hanging off a node already on the tour, and backing up along the stack splices it in at exactly the right place.

The slow version that people write first

Removing each used edge from the list with remove looks tidier and turns the algorithm into O(m * m) — a hundred thousand edges become ten thousand million steps.

The pointer is the whole difference. Never scan a list you have already scanned.

With arrows, count in and out separately

A directed tour that uses every arrow once exists when every node has as many arrows in as out — or when exactly one node has one extra out (the start) and one has one extra in (the finish).

Same counting argument: passing through uses one in and one out.

Python

n = 4
arrows = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 0)]

indeg = [0] * n
outdeg = [0] * n
for a, b in arrows:
    outdeg[a] += 1
    indeg[b] += 1

print(indeg)
print(outdeg)
print(all(indeg[i] == outdeg[i] for i in range(n)))

It prints

[2, 1, 1, 1]
[2, 1, 1, 1]
True

Where this is actually used

A De Bruijn sequence is a string containing every possible block of k letters exactly once — the shortest string that tries every PIN, and how DNA fragments are reassembled.

Build a graph whose nodes are blocks of k - 1 letters and whose arrows are blocks of k. An Euler tour of it is the sequence.

Python

blocks = ["00", "01", "10", "11"]
nodes = ["0", "1"]

for block in blocks:
    print(block, "goes from", block[0], "to", block[1])

It prints

00 goes from 0 to 0
01 goes from 0 to 1
10 goes from 1 to 0
11 goes from 1 to 1

The shortest string with every pair in it

Two nodes, four arrows, every degree balanced — so an Euler circuit exists, and walking it spells 00110. Five characters holding all four pairs.

Writing out all four pairs separately would take eight.

Python

text = "00110"
seen = []
for i in range(len(text) - 1):
    seen.append(text[i:i + 2])

print(seen)
print(sorted(seen) == ["00", "01", "10", "11"])

It prints

['00', '01', '11', '10']
True

The twin problem that nobody can solve

Every edge once is a degree count. Every node once — a Hamiltonian path — has no known fast test at all. No counting rule, no clever search: it is one of the famous hard problems.

The two questions look almost the same. One is linear time and one may be beyond computers for ever.

So brute force, cleverly

Unit 7 already did this. The state is (visited set, where you are) — a bitmask and a node — and the answer is 2 ** n * n * n instead of n factorial.

For 20 nodes that is 400 million against two million million million. Both are terrible; only one is possible.

Python

import math

for n in [10, 15, 20]:
    print(n, math.factorial(n), (1 << n) * n * n)

It prints

10 3628800 102400
15 1307674368000 7372800
20 2432902008176640000 419430400

Counting the routes that visit everything

dp[mask][here] is how many ways to have visited exactly mask and be standing on here. Start with only node 0 visited, and extend one node at a time.

On this five-node graph there are 6 routes from node 0 that reach every node.

Python

n = 5
adj = [[1, 2], [0, 2, 3], [0, 1, 3, 4], [1, 2, 4], [2, 3]]

dp = [[0] * n for mask in range(1 << n)]
dp[1][0] = 1

for mask in range(1 << n):
    for here in range(n):
        if dp[mask][here] == 0:
            continue
        for nxt in adj[here]:
            if (mask >> nxt) & 1:
                continue
            dp[mask | (1 << nxt)][nxt] += dp[mask][here]

full = (1 << n) - 1
print(sum(dp[full][i] for i in range(n)))

It prints

6

Checking it by listing them

Five nodes is small enough to try all 24 orders that start at node 0 and check each one — and it agrees: 6.

That is the honest way to trust a bitmask DP. Write the slow version, run both on the small case, and only then submit.

Python

n = 5
adj = [[1, 2], [0, 2, 3], [0, 1, 3, 4], [1, 2, 4], [2, 3]]

def walk(path):
    if len(path) == n:
        return 1
    total = 0
    for nxt in adj[path[-1]]:
        if nxt not in path:
            total += walk(path + [nxt])
    return total

print(walk([0]))

It prints

6