The garbage truck route
The garbage truck has to go down every street in the neighborhood exactly once and end up back where it started. Is that always possible?
- For each map, lock in your guess in the task: can it be done or not?
- Tap a corner to put the truck there.
- Tap the streets, one after another. Each street can be used only once.
Map and tasks
1. Vila Esperança
Route: not started yet.
Make your guess first. The map unlocks when you lock in your guess in the task.
Answer the questions in the task first. After that, Show counts shows how many streets meet at every corner.
Map 1: Vila Esperança
Can the truck go down every street exactly once and end up back where it started?
After your guess, tap a corner on the map and follow the streets.
Map 2: Jardim Paraíso
What about this neighborhood? Can the truck go down every street exactly once and end up back where it started?
If the truck gets stuck, undo or start over from another corner.
Map 3: Downtown
And Downtown? Can the truck go down every street exactly once and end up back where it started?
Count the streets at each corner
On the map, count the streets that meet at the corner in the question. After that, Show counts, below the map, shows the streets at every corner and fills in the last column of the table. Odd corners are corners with an odd number of streets.
| Map | Your guess | What happened | Odd corners |
|---|
Challenge: open a new street
In Vila Nova, the truck can't make a circuit. The city can open one new street, on one of the dashed lines. Which street makes a circuit possible?
After your guess, open the street with the buttons below the map and trace the circuit to prove it.
Decide by counting
Three new neighborhoods. In each one, count the streets at every corner and decide what the truck can do, before you trace anything.
After you lock it in, trace the route to check. The task is done when all three neighborhoods have a decision.
Extra challenge: Downtown
On the Downtown map, what is the smallest number of new streets that makes a circuit possible? Open streets and trace to prove it.
What's going on
This part unlocks when you finish the task where you count the streets at each corner.
The number of streets that meet at a corner is the degree of that corner. In math, the map is a graph: the corners are the vertices, and the streets are the edges.
Every time the truck passes through a corner, it comes in on one street and leaves on another. So the streets at that corner get used up two at a time. If the degree is odd, one street is left over at the end: either the truck leaves on it and never comes back, or it comes in on it and gets stuck. That's why only the corner where the route starts and the corner where it ends can have an odd degree.
A route that goes down every street exactly once and returns to the start is an Euler circuit. A route that goes down every street exactly once but ends at a different corner is an Euler trail. Both are named after Leonhard Euler, who solved a similar problem in the 1700s, about the seven bridges of the city of Königsberg. Here is the rule, for a neighborhood where you can get from any corner to any other:
- every corner has an even degree: there is an Euler circuit, starting at any corner;
- exactly two corners have an odd degree: there is no circuit, but there is an Euler trail, from one of those corners to the other;
- more than two corners have an odd degree: there is neither one nor the other.
Then go back to the tasks for the challenges: opening a new street, and deciding about three neighborhoods by counting alone.
For teachers
Objective
By the end, students can decide, by counting the streets at each corner, whether a map has a route that goes down every street exactly once and returns to the start. This is Euler's circuit theorem (section 12.5 of the book), with the case of exactly two odd corners, the Euler trail from section 12.6, as an extension. The problem faced by anyone who collects garbage, delivers mail, or sweeps streets is the Chinese postman problem, which the book mentions.
Prerequisites
Knowing what even and odd numbers are, and reading a simple map. Students don't need to have seen graphs before; the terms degree, vertex, edge, Euler circuit, and Euler trail appear in the explanation, after students have already played with the maps.
How to use in class
About 25 minutes. Project map 1 and ask the class for a guess before tracing; one student comes to the board (or calls out the corners) and completes the circuit. Let pairs try maps 2 and 3 for about 6 minutes, writing down their guess and result. Ask: on which map did nobody succeed? Did anyone finish the little house at a different corner? Where did they start? Then have them count the streets at each corner, and only after that turn on "Show counts" on the projector. Read the explanation with the class, do the Vila Nova challenge, and close with the three neighborhoods in the last task: each pair decides by counting alone and says the answer out loud, and only then does someone trace. Students who finish early move on to the extra challenge.
Common mistakes
Thinking it failed for lack of trying: a student who keeps trying Downtown without counting has this idea, and the count shows that the problem is the map. Thinking the starting corner doesn't matter: on the little house (Jardim Paraíso), it only works starting at E or F, the two odd corners. Returning to the start too early in Vila Esperança (from A to C, D, and back to A) and concluding it's impossible: every corner there is even, so the mistake is the order of the streets. Mixing up visiting every corner with going down every street; the activity points it out when this happens. In the extra challenge, thinking that opening more streets always helps: opening all four diagonals leaves four odd corners again.
Discussion questions
- Why can only the corners at the start and end of the route have an odd number of streets?
- Can a neighborhood have exactly one odd corner? (Hint: add up the degrees of all the corners. Each street counts twice in the sum, so the sum is always even.)
- If a neighborhood has no circuit, the truck has to repeat some streets. How do you choose which ones to repeat so it drives as little as possible?
- What other city services have the same problem as the garbage truck? And which ones need to visit every corner instead of every street?
Based on Contemporary Mathematics, OpenStax, sections 12.5 and 12.6, under the CC BY-NC-SA 4.0 license. This activity is under the same license. Access the book for free at openstax.org.