Science & Technology

This Map-Coloring Problem Was a Century-Old Mathematics Mystery

Say you're going to color a map. The only rule is that two adjacent regions of the map can't be the same color. How many colors do you need? Believe it or not, this is a problem that plagued mathematicians for more than 100 years — and it wasn't even solved until after humans set foot on the moon. How did we finally solve it? With a newfangled technology called the computer.

Coloring Outside the Lines

It shouldn't surprise anyone that the first person to pose this question wasn't a big-shot mathematician, but a student. In 1852, Francis Guthrie was a 21-year-old law student trying to color in a map of the counties of England when he noticed that, assuming no two bordering counties share a color, he needed at least four colors to color the whole map. This made him wonder if four colors might be enough to color any map. Since his younger brother Frederick was a student of actual big-shot mathematician Augustus De Morgan, Francis suggested Frederick bring it up to his teacher. De Morgan was intrigued and looped the rest of the mathematics community in on his curiosity.

Asking the question is one thing, but answering it ended up being incredibly tough. To prove you can color any map with four colors, for instance, you need to prove that you can color any map with six, and then five colors. Those two proofs were simple: It turns out that you can't make a map where every region has six or more neighbors; at least one region has to have five or fewer. That means that five colors are enough to color any map. That puts you one step closer to the four-color theorem. But how do you prove that any map only needs four colors? You could look at all of the possible maps and figure out if any of them need five colors, but that would take an unbelievable amount of time — the kind of time that only a mathematician would put in, perhaps?

The four color theorem at work.

Computers, Schmomputers

By the 1900s, mathematicians had broken mapmaking down to a simpler set of rules and eventually were able to reduce the sheer number of possible maps to a manageable set of types that could be classified and colored one by one. Of course, manageable is in the eye of the beholder — that set still contained 9,000 maps. By the 1970s, computers were becoming more accessible, so mathematicians were able to use algorithms to narrow that set down even more. In 1976, mathematicians Kenneth Appel and Wolfgang Haken reduced the number to 1,936, then tested every single one to make sure they could all be filled in with four colors. They checked and re-checked their findings on different computers with different algorithms, and their results were the same. Finally, they had a proof that showed that you can't have a map with a number of regions that would require five colors.

This was the first time a computer had been used to solve a math problem, and it was understandably controversial. According to the University of Cambridge, "Many mathematicians and philosophers claimed that the proof was not legitimate. Some said that proofs should only be 'proved' by people, not machines, while others, of a more practical mind questioned the reliability of both the algorithms and the ability of the machines to carry them out without error." Of course, the four-color theorem had been "proved" by people twice already, and both proofs had been faulty. Since then, mathematicians have embraced computers and computer algorithms, but that doesn't mean the argument is obsolete. It has echoes in the debates over autonomous vehicles today; people are nervous about the risks of letting a computer drive, even though human error is the reason for 94 percent of car crashes. Distrust of technology is a tale as old as technology itself.

Get stories like this one in your inbox or your headphones: sign up for our daily email and subscribe to the Curiosity Daily podcast

Love math mysteries? Check out "The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles Of Our Time" by Keith J. Devlin. We handpick reading recommendations we think you may like. If you choose to make a purchase, Curiosity will get a share of the sale.

Written by Ashley Hamer May 8, 2017

Curiosity uses cookies to improve site performance, for analytics and for advertising. By continuing to use our site, you accept our use of cookies, our Privacy Policy and Terms of Use.