The Seven Bridges of Königsberg

4Degrees

The degree deg(v) of a vertex v is the number of edge ends that touch it. Equivalently, it is the number of bridges leaving that landmass.

As a check, use the handshake lemma. Each edge has exactly two ends, and each end adds 1 to the degree of one vertex. So for every graph,

∑_{v ∈ V} deg(v) = 2 |E|,
and here 3 + 5 + 3 + 3 = 14 = 2 × 7.

One consequence: the sum of all degrees is even, so every graph has an even number of odd-degree vertices.

6Why it matters in informatics

Euler’s theorem replaces a search with a count. You do not need to try any routes, only to count degrees:

from collections import Counter

def euler_kind(edges):
    """Classify a connected multigraph given as a list of edges (u, v)."""
    degree = Counter()
    for u, v in edges:
        degree[u] += 1
        degree[v] += 1
    odd = sum(1 for d in degree.values() if d % 2 == 1)
    if odd == 0:
        return "Eulerian circuit"
    if odd == 2:
        return "Eulerian path"
    return "neither"

koenigsberg = [("A", "B"), ("A", "B"), ("B", "D"), ("B", "D"),
               ("A", "C"), ("B", "C"), ("C", "D")]
print(euler_kind(koenigsberg))  # neither: four odd vertices

This runs in O(V + E) time: one pass over the edges, then one over the vertices. A complete check also verifies that all edges belong to a single connected component, using one breadth-first or depth-first search, which is also O(V + E). A naive search that tries every order of the edges can examine up to E! sequences. That is 7! = 5,040 for Königsberg, but 20! ≈ 2.4 × 10¹⁸ for a graph with only 20 edges.

The same idea appears throughout computer science:

• Hierholzer’s algorithm builds an Eulerian circuit in O(E) time. Follow unused edges until you return to the start. Then, from any vertex on that circuit that still has unused edges, build another circuit and splice it in.
• The Chinese postman problem asks for the shortest closed walk that uses every edge at least once, as for mail delivery, snow ploughs or street sweepers. On undirected graphs, it is solved in polynomial time. Pair up the odd vertices with a minimum-weight perfect matching, weighted by shortest-path distance. Then walk the shortest path between each matched pair a second time.
• De Bruijn graphs in genome assembly: DNA sequencers read millions of short fragments, which are cut into overlapping substrings of length k. Each substring becomes a directed edge from its first k − 1 letters to its last k − 1 letters. Rebuilding the genome then becomes a search for an Eulerian path. In directed graphs, the condition is that in-degree equals out-degree at every vertex, except that the start has one extra outgoing edge and the end has one extra incoming edge.
• The Hamiltonian contrast: change “every edge exactly once” to “every vertex exactly once” and no simple degree test works anymore. Deciding whether a graph has a Hamiltonian path is NP-complete. No polynomial-time algorithm is known, and finding one would prove P = NP.