Case Study: Auditing a Street-Sweeper Route with Euler's Theorem

"The problem, then, is not 'can it be done?' but 'can it be done before the heat death of the universe?'" — a sentiment every working programmer eventually internalizes

Executive Summary

A city's Public Works department runs a fleet of street sweepers. Each sweeper is assigned a neighborhood and told to clean every street and return to its depot — ideally driving each street exactly once, because every repeated pass is wasted fuel, wasted time, and an extra pass of a heavy truck down a residential street. A contractor's routing software keeps producing routes that repeat streets, and the department wants to know: is the software just bad, or is a no-repeats route impossible for this neighborhood? And if it's impossible, what is the minimum fix?

This is an analysis problem, not a build problem. We will not write a routing optimizer. Instead we will take a real street network, model it as a graph, and use Euler's theorem (§30.2) to diagnose the situation precisely: decide whether a no-repeats closed route (an Euler circuit) exists, and if not, compute exactly how many streets must be repeated and where. The payoff is the difference between "the software is buggy" and "no software on Earth can do better, because the network's degrees forbid it" — a distinction you can only make with a proof, not a test (theme two of the book).

Skills applied

• Modeling a physical network (intersections, streets) as a graph (Chapter 27).
• Applying Euler's theorem to decide Euler-circuit/path existence by counting odd-degree vertices (§30.2).
• Verifying connectivity before invoking the theorem (Chapter 28) — the easy-to-forget half of the rule.
• Quantifying the minimum repeated mileage when no Euler circuit exists (the "route inspection" idea).
• Separating a tractable diagnosis ($O(V+E)$) from an intractable optimization, and recognizing which is which.

Background

The scenario

The Maplewood neighborhood is a small grid with a few diagonal cut-throughs. Public Works models it as a graph: each intersection is a vertex, each street segment between two intersections is an edge. The sweeper must traverse every edge and return to the depot at intersection $D$.

Here is the network. There are seven intersections $\{D, A, B, C, E, F, G\}$ and the following street segments (edges). The street network is a multigraph in spirit — a boulevard with a median that must be swept on both sides could be two edges — but Maplewood happens to be a simple graph:

Ten streets, seven intersections. The contractor's software keeps returning routes of length 11 or 12 (i.e., repeating one or two streets). Public Works wants an audit: should a length-10 route (each street once) that returns to $D$ be possible?

💡 Intuition: Strip the map down exactly as Euler did with Königsberg (§30.1). Street lengths, one-way signs, and geography are irrelevant to the existence question. What matters is only which intersections connect to which, and how many streets meet at each intersection — the degrees.

Why this matters

"Clean every street and come back" is an Euler circuit problem, one of the genuinely tractable results in this chapter. Unlike the delivery driver's Hamilton/TSP nightmare (§30.5), the sweeper's feasibility question has a fast, provable answer. Getting the audit right means Public Works can either (a) tell the contractor "your software is leaving mileage on the table — a perfect route exists, demand it," or (b) tell the city council "no perfect route exists for this neighborhood; the unavoidable minimum is X extra miles, and here's the math." Both are decisions that testing routes could never settle — you cannot test infinitely many possible routes — but a proof settles instantly.

Phase 1: Build the graph and compute degrees

The entire audit hinges on the degree of each intersection. Let's tally them by hand from the edge list, then in code. The degree of an intersection is the number of street segments meeting there.

Walking the edge list:

• $D$ appears in edges 1 ($D$–$A$), 2 ($D$–$B$) → $\deg(D) = 2$.
• $A$ appears in 1 ($D$–$A$), 3 ($A$–$B$), 4 ($A$–$C$) → $\deg(A) = 3$.
• $B$ appears in 2 ($D$–$B$), 3 ($A$–$B$), 5 ($B$–$C$) → $\deg(B) = 3$.
• $C$ appears in 4 ($A$–$C$), 5 ($B$–$C$), 6 ($C$–$E$), 7 ($C$–$F$) → $\deg(C) = 4$.
• $E$ appears in 6 ($C$–$E$), 8 ($E$–$F$), 9 ($E$–$G$) → $\deg(E) = 3$.
• $F$ appears in 7 ($C$–$F$), 8 ($E$–$F$), 10 ($F$–$G$) → $\deg(F) = 3$.
• $G$ appears in 9 ($E$–$G$), 10 ($F$–$G$) → $\deg(G) = 2$.

Now in code, building the adjacency from the edge list and tallying degrees:

edges = [("D","A"),("D","B"),("A","B"),("A","C"),("B","C"),
         ("C","E"),("C","F"),("E","F"),("E","G"),("F","G")]

adj = {}
for u, v in edges:
    adj.setdefault(u, []).append(v)
    adj.setdefault(v, []).append(u)

degrees = {v: len(adj[v]) for v in sorted(adj)}
print(degrees)
# Expected output:
# {'A': 3, 'B': 3, 'C': 4, 'D': 2, 'E': 3, 'F': 3, 'G': 2}

A quick sanity check using the handshaking lemma (Chapter 27): the degree sum is $3+3+4+2+3+3+2 = 20 = 2 \times 10$, exactly twice the number of edges. Good — we've miscounted nothing.

🔄 Check Your Understanding Before reading on: how many intersections have odd degree? From §30.2, what does that count immediately tell you about whether an Euler circuit exists?

Answer

Odd-degree intersections: $A(3), B(3), E(3), F(3)$ — four of them. By Euler's theorem, an Euler circuit requires every vertex even, so four odd vertices means no Euler circuit exists. (Worse than the Euler-path case, which tolerates exactly two.)

Phase 2: Decide Euler-circuit existence (and check connectivity first)

The pitfall in §30.2 is loud: even degrees alone are not enough — the graph must also be connected. So the audit is a two-part test. We check connectivity, then parity.

Connectivity. Run a traversal (BFS or DFS from Chapter 28) from any intersection and confirm every intersection is reached. Tracing a DFS from $D$: $D \to A \to B$ (via edge 3) $\to C \to E \to F \to G$ — all seven reached. Maplewood is connected. (In code you would call bfs(g, "D") from the Toolkit and check the visited set has size 7; it runs in $O(V+E)$.)

Parity. From Phase 1, four intersections have odd degree. Putting both parts together with the decision logic of §30.2:

def euler_diagnosis(adj):
    """Decide Euler status assuming connectivity has been checked separately."""
    odd = sorted(v for v in adj if len(adj[v]) % 2 == 1)
    if len(odd) == 0:
        return "Euler circuit exists (every street once, return to start)"
    if len(odd) == 2:
        return f"Euler path exists between {odd[0]} and {odd[1]} (no closed route)"
    return f"No Euler path or circuit: {len(odd)} odd-degree intersections {odd}"

print(euler_diagnosis(adj))
# Expected output:
# No Euler path or circuit: 4 odd-degree intersections ['A', 'B', 'E', 'F']

The verdict so far. A perfect closed sweep — every street exactly once, back to the depot — is impossible for Maplewood. This is not the software's fault; it is a structural property of the street network. With four odd-degree intersections, no algorithm, however clever, can avoid repeating streets. That is the audit's first hard finding, and it took an $O(V+E)$ scan, not a search.

⚠️ Common Pitfall: Had we skipped the connectivity check and only counted parities, we'd be giving an incomplete audit. A neighborhood could have all-even degrees yet split into two disconnected clusters (say, a footbridge was demolished), in which case "every degree even" would wrongly suggest an Euler circuit exists. Always report both halves of the rule. Maplewood passes connectivity, so here parity is the binding constraint — but the audit must verify both.

Phase 3: Quantify the minimum unavoidable repeat

"Impossible" is not the end of a good audit. The next question Public Works actually cares about: if we must repeat some streets, what is the fewest we can get away with? This is the classic route inspection problem (often called the Chinese Postman Problem): find the cheapest closed walk that covers every edge, allowing repeats.

The key insight builds directly on Euler's theorem. An Euler circuit needs every degree even. We have four odd vertices: $A, B, E, F$. Each street we re-sweep is like adding a duplicate edge, and adding an edge flips the parity of its two endpoints. To make all degrees even, we must add duplicate edges that, together, flip exactly the four odd vertices to even — which means pairing up the odd vertices and duplicating a path between each pair.

With four odd vertices there are three ways to pair them:

• $\{A,B\}$ and $\{E,F\}$
• $\{A,E\}$ and $\{B,F\}$
• $\{A,F\}$ and $\{B,E\}$

For each pairing, the cheapest way to "connect" a pair is to re-sweep the shortest path between them; the total extra mileage is the sum of the two shortest-path lengths. The minimum over the three pairings is the unavoidable repeat. Let's reason it out using street-segment counts as distances (each edge = 1 block, for simplicity).

Shortest paths (number of blocks) between the odd intersections:

• $A$ to $B$: direct edge 3 → 1 block.
• $E$ to $F$: direct edge 8 → 1 block.
• $A$ to $E$: $A\to C\to E$ → 2 blocks.
• $B$ to $F$: $B\to C\to F$ → 2 blocks.
• $A$ to $F$: $A\to C\to F$ → 2 blocks.
• $B$ to $E$: $B\to C\to E$ → 2 blocks.

Now total each pairing:

The minimum is 2 extra blocks, from the pairing $\{A,B\} + \{E,F\}$. So the best possible sweeper route covers all 10 streets plus 2 repeated streets (the $A$–$B$ segment and the $E$–$F$ segment), for a total of 12 traversals.

# Audit conclusion, computed by hand above and recorded for the report:
total_streets   = 10
min_extra       = 2          # cheapest odd-vertex pairing: {A,B}+{E,F}, each 1 block
best_route_len  = total_streets + min_extra
print(best_route_len, "traversals; repeats =", ["A-B", "E-F"])
# Expected output:
# 12 traversals; repeats = ['A-B', 'E-F']

🔗 Connection. Notice the audit just used shortest paths (Chapter 29) and the parity logic of Euler's theorem together. The route-inspection problem is solved by reducing it to a minimum-weight matching of the odd vertices (Chapter 34) — pairing them so the total shortest-path cost is least. Crucially, route inspection is tractable (polynomial time), unlike its vertex-analogue TSP. Swapping "cover every edge" for "visit every vertex" again flips a problem from easy to hard — the central asymmetry of this chapter.

Phase 4: What the contractor's software should have done

Now we can grade the contractor. The software returned routes of length 11 and 12.

• A length-12 route is optimal — it matches our proven minimum. If the software returns 12 and the repeated streets are $A$–$B$ and $E$–$F$ (or any equally good pairing), it is doing the best any algorithm can.
• A length-11 route would be impossible and indicates a bug — it would mean only one street was repeated, flipping only two of the four odd vertices to even, leaving two odd vertices, which (by Euler's theorem) still cannot support a closed route. So if the software claims a valid length-11 closed sweep, it is either miscounting or producing an open route that doesn't return to the depot.

This is the audit's real value. Without the theorem, Public Works might have demanded a length-10 route that cannot exist, or accepted a length-11 route that is secretly invalid. With the theorem, the contract can specify the provably correct target: a closed route of exactly 12 traversals, and the acceptance test becomes "covers all 10 streets, repeats exactly 2, returns to $D$."

🐛 Find the Error. A junior analyst writes in the draft report: "Since four intersections have odd degree, we just need to add four duplicate streets — one at each odd intersection — to make every degree even." What's wrong, and what's the correct count?

Answer

Adding a duplicate edge flips the parity of two vertices at once (its two endpoints), not one. To fix four odd vertices you pair them and duplicate a path between each pair — that's two paths, not four edges. The junior's count double-counts. The correct minimum here is 2 extra blocks ($A$–$B$ and $E$–$F$), as Phase 3 showed. The deeper point: parity is fixed in pairs, which is exactly why the number of odd-degree vertices is always even (Exercise 30.8).

Discussion Questions

1. The audit declared a perfect route impossible using only degrees. Suppose Public Works could afford to build one new street segment. Which single new street would make an Euler circuit possible, and why? (Hint: you need to eliminate odd vertices in pairs — can one new edge fix two of them?)
2. We treated every street as 1 block. If streets have different lengths, how does Phase 3 change? Which chapter's algorithm do you now need for the "shortest path between odd vertices" step, and does the problem stay tractable?
3. The route-inspection problem (cover every edge cheaply) is polynomial-time solvable, but TSP (visit every vertex cheaply) is NP-hard. In your own words, why does this one-word change in the problem statement cause such a dramatic change in difficulty? Tie your answer to the §30.4 "local versus global" intuition.
4. The connectivity check ran in $O(V+E)$ and the parity count ran in $O(V+E)$. Argue that the entire feasibility audit is therefore polynomial in the size of the street network — and contrast that with what an audit of "find the cheapest delivery route" (TSP) would cost.
5. Suppose the sweeper does not need to return to the depot (it parks wherever it finishes). How does the audit change? Which Euler result now applies, and for Maplewood (four odd vertices) is a no-repeats open route possible?

Your Turn: Extensions

• Option A (re-audit a fixed network). Add the single street from Discussion Question 1 to the edge list, recompute all degrees by hand, and re-run euler_diagnosis. Confirm in an # Expected output: comment that the network now reports an Euler circuit. State the new degree sequence.
• Option B (build the actual route). For the fixed network (all even degrees), hand-trace Hierholzer's algorithm (the euler_circuit constructor from the §30.2 Project Checkpoint) starting at $D$, and write out one valid Euler circuit as a sequence of intersections. Verify it uses each street exactly once.
• Option C (generalize the minimum-repeat logic). Write a function min_extra_blocks(odd, dist) that takes the list of odd-degree vertices and a dict of pairwise shortest-path distances, enumerates all ways to pair the odd vertices, and returns the minimum total. Test it on Maplewood's four odd vertices and confirm it returns 2. (Note: for many odd vertices this enumeration explodes — research why minimum-weight matching, not brute-force pairing, is used in practice; Chapter 34.)
• Option D (the disconnected trap). Construct a small edge list with all-even degrees that is disconnected, and show that euler_diagnosis (which assumes connectivity) would give a misleading answer. Add a connectivity guard and re-run. This hardens the audit against the §30.2 pitfall.

Key Takeaways

1. "Clean every street and return" is an Euler-circuit question — and it's tractable. The whole feasibility audit is an $O(V+E)$ degree count plus an $O(V+E)$ connectivity check. No route search is needed to decide existence.
2. Check connectivity and parity — both, every time. Even degrees alone do not guarantee an Euler circuit; the graph must also be connected. A complete audit reports both.
3. "Impossible" has a quantitative refinement. With four odd vertices, no perfect route exists, but the minimum unavoidable repeat is computable: pair the odd vertices to minimize total shortest-path length (here, 2 extra blocks). That turns "the software is bad" into a precise, provable target.
4. A proof settles what testing cannot. No finite set of test routes could establish that a perfect sweep is impossible; Euler's theorem settles it in one parity argument — theme two of the book.
5. One word changes everything. Covering every edge cheaply (route inspection) is polynomial; visiting every vertex cheaply (TSP) is NP-hard. Recognizing which problem you actually have is the engineering judgment this chapter teaches.