Math

How A Discovery About Coloring Maps Changed Mathematics Forever

News: The Curiosity Podcast is here! Subscribe on iTunes, Stitcher, Google Play Music, SoundCloud and RSS.

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.

Related: Are Math Equations Beautiful? Euler's Identity Makes Mathematicians Swoon

Advertisement

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 theorm 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.

Related: Road Trip! Why Mathematicians Are Vexed By The Traveling Salesman Problem

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.

Love getting smarter? Sign up to our newsletter and get our best content in your inbox!

Watch And Learn: Our Favorite Content About Math Problems

The Four Color Map Theorem

Advertisement