How many colors do you need to shade a map?

The small island nation of Seedonia is organized into three provinces: Sciville, Connexia, and Collabdale.

One year, Connexia’s two best soccer teams played to a 1-1 tie in the Provincial Championship. Being unable to decide which team to send to the National Tournament, the people of Connexia voted to split the province into North Connexia and South Connexia so they could send both teams, one from each of the new provinces.

Some years later, for reasons that are not clear, Collabdale split into Upper Collabdale and Lower Collabdale. Map publishers in Seedonia became concerned about the rising cost of printing maps, since they had already gone from three to four colors when Connexia split. How could they avoid using the same color for adjacent provinces without adding a fifth color?

One mapmaker solved the problem like this:

Moreover, he claimed that he could also color the ocean, which in earlier maps had been left blank, without adding a color. He even claimed that no matter what course Seedonia’s political future took, he could color any map, regardless of how many provinces there were and no matter how they drew their borders, using only four colors. No two adjacent provinces would have to be in the same color.

Is he correct? Can you come up with a map—real or imaginary—that requires more than four colors? The key requirement is that no region can share an edge with another region of the same color. Corner touching is OK. For example, this map uses only two colors and doesn’t violate the rules:

Try it with a friend. One of you can draw a difficult map for the other to try to color.

If you can’t find a map that requires more than four colors, can you prove that no more than four are ever needed?

Make up some puzzles like these and send them in with your solutions. We’ll post them here in the SEED Science Center.