The Muddy City

A City With No Roads

Once there was a city.
It had no roads.
When it rained, the ground got muddy.
Cars got stuck in the mud.
People got mud on their boots.

The mayor wanted to help.
She wanted to pave some streets.
Paving means covering the ground with hard stones.
This stops the mud problem.

But paving costs money.
The city also wanted a new pool.
So the mayor made two rules.

Rule one: every house must connect to every other house.
People can walk on paved roads only.
They can pass by other houses too.

Rule two: use as few paving stones as possible.
Spend the least money you can.

The Map

There is a map of the city.
It shows all the houses.
It shows paths between houses.
Each path has a number.
The number tells how many stones it needs.

Your job is fun.
Find the smallest number of stones.
Make sure every house connects.

Try It Yourself

Get a copy of the map.
Get some counters or cardboard squares.
Put counters where you think roads should go.

Try to use the fewest counters.
Keep trying to do better.
There is more than one good answer.
Some answers use the same number of stones.

Two Good Ways to Solve It

Way one: Start with no roads at all.
Add the shortest road first.
Keep adding short roads.
Only add a road if it connects new houses.
Don't add a road if houses already connect.

This way works very well.
It helps you find a great answer.

Way two: Start with all roads paved.
Then take roads away.
Take away roads you don't need.
This way also works.
But it takes more work.

Talk About It

Talk with your class.
How did you solve the puzzle?
What ways did you try?

A New Way to Draw Cities

We can draw cities in a simpler way.
Houses become circles.
Roads become lines.
Numbers by the lines show road length.

Smart people call this picture a graph.
A graph shows how things connect.
This is a different kind of graph.
It is not a bar graph with data.

How Many Roads Do We Need?

Think about this question.
If a city has many houses, how many roads are needed?

Here is the answer.
Count the houses. Call that number "n."
You always need n minus 1 roads.
That is enough to connect every house.
One more road would not be needed.

Real Cities and Networks

Look for real networks around you.
Roads between cities are a network.
Airplane flights are a network too.

But there's something to remember.
This puzzle only makes roads short.
It does not make roads convenient.
Sometimes a short way is not the easy way.

Smart people have other methods too.
Some find the fastest way between two places.
Some find a way to visit every place.
Drawing a graph is a good first step.

Why This Matters

Think about electricity, gas, or water.
New homes need these things.
Wires or pipes must connect every house.

The path does not have to be perfect.
It just needs to connect all houses.
Using the least wire or pipe saves money.

This is called the minimal spanning tree problem.
Minimal means "smallest."
Spanning means "connecting everything."
Tree means the connections branch out, like a tree.

Used in Many Places

This idea helps with many things.
It helps with computer networks.
It helps with telephone lines.
It helps with oil pipelines.
It helps with airplane routes.

But remember: cost is not everything.
Sometimes convenience matters too.

This idea also helps solve bigger puzzles.
One puzzle asks: what is the shortest trip?
A trip that visits every single place.

A Smart Method

There is a smart way to solve this puzzle.
Start with no connections at all.
Add the shortest connections first.
Only add ones that connect new places.

This method has a name.
It is called Kruskal's algorithm.
It is named after J.B. Kruskal.
He shared this method in 1956.