Substitute Lesson Plan: The Muddy City — Minimal Spanning Trees

Objective

Students will practice puzzle solving, optimization, and planning by figuring out the minimum number of paved roads needed to connect every house in a city, while spending as few paving stones (resources) as possible.

Materials

• Copies of "The Muddy City" blackline master (one per student, enlarged if possible)
• Counters or small squares of cardboard (approximately 40 per student) to represent paving stones
• (Optional) chart paper or board to record different solutions found by students

Warm-up (~5 min)

Tell the class the story of the muddy city: once there was a city with no paved roads. After rainstorms, the ground got so muddy that cars got stuck and people's boots got dirty. The mayor wants to pave just enough streets so that everyone can get from their house to anyone else's house — but doesn't want to spend more paving stones than necessary, because the city also wants to build a swimming pool. Ask students: "Why might it be a bad idea to pave every single road?" (Costs too many paving stones.) Explain that the number of paving stones between two houses on the map shows how expensive it is to pave that road.

Main Activity (~25 min)

1. Hand out one copy of the blackline master to each student along with a pile of counters.
2. Explain the task: students should place counters on the roads they choose to pave. The goal is to connect every house to every other house (possibly through other houses) using as few total paving stones as possible. Remind them the bridge does not need to be paved.
3. Let students work individually (or in pairs) to try placing counters on different roads, counting up the total paving stones used, and trying to beat their own previous total.
4. As students work, circulate and announce improvements to the whole class ("Someone just found a solution using only ___ stones!") to encourage friendly competition and refinement.
5. Let students know that an optimal solution exists using 23 paving stones, and that there is more than one way to achieve this same minimum total — so different students' maps may look different but still be equally correct.
6. With about 5 minutes left in this segment, ask a few students to describe the strategy they used. Guide discussion toward two common strategies:
7. Building up: Start with an empty map and add the shortest available roads one at a time, but only if they connect a house that isn't already linked to the network. (This always finds an optimal solution.)
8. Cutting down: Start with every road paved, then remove roads that aren't needed. (This also can work, but takes more effort.)

Wrap-up / Exit Ticket (~10 min)

Ask each student to write down or say aloud:

1. What was the total number of paving stones in the solution you found?
2. In your own words, describe one strategy you used to decide which roads to pave.
3. Why do you think it's useful for a real city to plan roads (or pipes, or wires) this way — connecting every house while using as little material as possible?

Collect written answers as an exit ticket, or discuss as a class if time is short.

If Time Remains

Show students the more abstract "graph" version of a muddy city, where houses are drawn as circles and roads are drawn as lines with numbers showing their length. Ask them to try solving this new version using the same strategy (adding the shortest connections first, without linking houses that are already connected). Discuss how this simpler drawing represents the same kind of problem as the original map, just in a different form.