📍 Scene Setup
The city's inspection robots need to survey every road in the district, but the route planning system requires all topology data to be verified before a robot can be assigned to any sector.
Josh is on shift as route coordinator. Six district maps are waiting for sign-off. Each one needs the right traversability data before a robot can be deployed.
📋 Traversability Rules
0 odd-degree vertices
Euler circuit, returns to start
2 odd-degree vertices
Euler path, different start/end
4+ odd-degree vertices
Not traversable in one pass
Handshaking: sum of degrees = 2 × edges · Euler's formula: v − e + f = 2
1
District 1, Odd Vertex Count
Sector Alpha has 5 intersections. Their road-connection counts (degrees) are: 4, 3, 2, 3, 2.
How many of these intersections have an ODD number of connections?
Identify which degree values are odd numbers, then count them.
💡 Odd numbers in the list: 4 (even), 3 (odd), 2 (even), 3 (odd), 2 (even). How many odd ones?
✅ 2 odd-degree vertices. That means an Euler path is possible, but not a circuit.
2
District 2, Edge Count
Same sector, degrees are still 4, 3, 2, 3, 2.
How many road segments (edges) are in this sector?
Use the handshaking lemma: sum of degrees = 2 × edges.
💡 Sum of degrees = 4+3+2+3+2 = 14. Then edges = 14 ÷ 2 = ?
✅ 7 roads. Sum = 14, divided by 2 = 7 edges.
3
District 3, Planar Face Count
Sector Beta's road map is drawn as a planar diagram. It has 6 intersections and 8 road segments.
Using v − e + f = 2, how many regions does the map divide the page into?
Faces include the outer unbounded region, don't forget it.
💡 v − e + f = 2 → 6 − 8 + f = 2 → f = 2 − 6 + 8 = ?
✅ 4 faces. Using v − e + f = 2: f = 2 − 6 + 8 = 4.
4
District 4, The Königsberg Problem
The famous Königsberg bridge problem (solved by Euler in 1736) involved 4 land masses connected by 7 bridges. Every single land mass had an odd number of bridge connections.
How many odd-degree vertices did the Königsberg graph have?
This is why no one could traverse all 7 bridges exactly once, the number of odd vertices made it impossible.
💡 There were 4 land masses and every one had odd degree. So how many odd-degree vertices?
✅ 4 odd-degree vertices, that's why it's impossible. You need 0 or 2 odd vertices for traversal.
5
District 5, Larger Planar Map
Sector Gamma's map is a larger planar graph with 8 intersections and 11 road segments.
How many faces does the planar diagram have?
Same formula: v − e + f = 2.
💡 8 − 11 + f = 2 → f = 2 − 8 + 11 = ?
✅ 5 faces. f = 2 − 8 + 11 = 5.
6
District 6, Final Edge Verification
The final sector has 7 intersections. Their connection counts are: 2, 4, 6, 4, 2, 4, 4.
How many road segments (edges) are in this sector?
Sum all the degrees, then divide by 2.
💡 Sum = 2+4+6+4+2+4+4 = 26. Edges = 26 ÷ 2 = ? Also note: all degrees are even, so an Euler circuit is possible here!
✅ 13 roads. Sum = 26, edges = 13. All even degrees → Euler circuit, the robot returns to its depot!
🤖
All Districts Cleared!
Every sector has been verified. The inspection robots are deployed, routes confirmed. Josh's traversability analysis was flawless from Sector Alpha to the final district.