The Four Color Problem: the Illustrious History

Remember being a kid being dragged to a restaurant with grownups? The one consolation was when they'd hand you a paper placemat with the outline of the US or a parrot or something and that set of four crayons. Why was it always only four crayons? Come on, Friendly's, more than half a billion in revenues and you couldn't give us one more dang crayon? Dang! Well, turns out you really didn't need to complain so much, at least if you were going for efficiency in your coloring practice. Four crayons isn't a whole lot, but there's a pretty deep math theorem that says it's enough.

Theorem: Four crayons suffice.

But okay, we should probably be clearer about what that means. Let's think of the uncolored picture on the placemat like a map. You can use whatever color you want in each region, but you don't want two regions that border each other to get the same color. So let's restate the theorem with this constraint.

Theorem: Suppose you have a picture, consisting of any number of regions, that you want to color so that no two bordering regions get the same color. Then four crayons suffice.

And if that isn't applied math, I don't know what is. If you doubt the direct applicability of this theorem to your life, just buy yourself a grown-up coloring book and four colored pencils. It should be noted that though you'll never need more than four colors, it's not always easy to actually find a way to color a picture with only four. There was even a famous April Fools' Joke gone awry in which Martin Gardner published a picture that they claimed required five colors to color, and a bunch of mathematicians actually believed this meant that the theorem had been disproven. Here's Gardner's picture. See if you can color it using only four colors.

Fig. 1. This picture requires five colors to color, haha jk lol April Fool's it only takes four.

By the way, can we think of any uncomplicated examples where we need four? If you draw a few simple pictures without thinking about it too hard, you may not end up with anything that requires more than three colors. To illustrate where three don't suffice, here's a picture of a bird. 

Fig. 2. This is a bird, okay?

You might be wondering if this is really a picture of a bird and if so, what is with that middle thing that has to be its wing, and can a bird with a wing that looks like a potato fly or is this one of those flightless things like a dodo or a penguin, and my answer to you is that we're talking about MATHEMATICS here, not art or zoology, so focus. Here is an example of how we can color this bird using only four colors, which is all this tuber-winged air skunk is good for right now.

Fig. 3. Now it's obviously a bird, right?

Convince yourself that you couldn't get away with three colors here. (The problem is with the "wing" in the middle. It's touching three other regions, each of which are touching each other, so coloring those four regions with any three colors would necessarily result in two bordering regions sharing a color. I don't know why the mouth-triangle and the eye are red, okay, so stop asking. Maybe the bird is a demon and it bathes its flesh-tearing beak in the blood of the vanquished in sacrifice to its unholy idol. Look, you're getting really distracted here. We have to get back to the math.)

Okay, so four colors are sometimes necessary, and the theorem---clearly true because it is in bold---tells us that we'll never need more than that. The theorem is so easy to state that you might think this problem is not very substantive. To address that, let's talk a little about this problem's lengthy and colorful (ha, ha) history, which should quickly give the idea that proving that theorem is going to be Really Dang Hard.

Fig. 4. How it all went down.

It's 1852 and Francis Guthrie, a future-mathematician-slash-botanist in London, is coloring a map of the counties of England, because math grad school leaves you with a lot of free time. Hold up, he thinks. He's in England though so it comes out, Hark! Verily! What if like, one day, there were chain restaurants that distracted small children from their ennui with sets of crayons? How many crayons shall suffice? Based on his map, I guess, the answer seemed to be four, and he couldn't come up with a map that needed more than that, and lo!---a conjecture was born. A couple of years later, he (or maybe his brother? or maybe someone else entirely with the same initials as him?) published the problem in The Athenaeum, the New Yorker of 19th century London, but fancier because there are three vowels in a row in its name.  But nobody cares what a grad student thinks, and what kind of self-respecting fancy pants needs to concern himself with such paltry questions? (Fancy people have lots of crayons.) So it wasn't until Guthrie's super-famous advisor Augustus De Morgan took an interest in the problem that people really got into it.

De Morgan wrote to this guy, Sir Hamilton, and told him about the problem. Sir Hamilton wrote back,

I am not likely to attempt your quaternion of colour very soon.

Because that is how people talked and it was awesome. So after sitting on it for a few more years, De Morgan published the same problem in the same dang magazine in 1960, and that got attention. Francis was probably pissed that his advisor stole his glory, though.

So now all these high-powered mathematicians are into it, but nothing happens for a while. And then, 19 years after De Morgan's publication, this barrister Alfred Kempe comes out of nowhere with a proof that impresses the pants off all these hoity-toities. Barrister is British for "lawyer in a wig" I'm guessing. Everyone is impressed as heck. Francis Guthrie was a barrister for a while too, by the way. They were both trained mathematicians as well, but the wig game isn't as strong in that industry.

The next year, another guy comes on the scene with another proof. This guy, Peter Guthrie Tait, is actually a physicist. He also says something like,

The four color conjecture is true if and only if no snarks are planar.

Nobody knows what he's talking about, so they just nod. By the way, Tait studied the ozone, which is kinda neat, and quaternions, which are weird kinds of numbers. He also hung out with Sir Hamilton from earlier and was really into golf.

Things are pretty good for a while after that. But then in 1890, Percy Heawood finds a flaw in Kempe's proof, and then in 1891, Julius Petersen finds a flaw in Tait's proof, and we're left totally proofless. Heawood is a gloriously mustachioed but tiny little dude who wears a cape, carries a ratty old handbag, and always brings his little dog to his lectures. Also, he goes by Pussy, so.

Pussy salvages Kempe's proof somewhat and uses it to prove the Five Color Theorem by using something called Kempe chains. The Five Color Theorem says that five colors suffice to color any picture (with the same constraints we made earlier). The argument is pretty short and sweet and is taught in undergrad math classes now. But back in 1891, we're still nowhere with the Four Color Problem, and over the next 64 years pretty much all that happens is that this guy Hugo Hadwiger comes up with a problem that's a vast generalization of this one, and it's still unsolved, and it just serves to depress everyone further.

Meanwhile, in Germany, Heinrich Heesch is doing his thing at his university, and then the 1930's come along and the Nazis say that you can't work in a university unless you become a member of the Nazi party. (Hitler tries to do a lot of crazy stuff at this point, and we'll just fast forward.) Heesch decides on a firm no thanks to that, and quits. He moves into his parents' basement in 1935, where he stays until 1948 (which seems longer than strictly necessary, given that WWII ends in 1945). When he emerges, he's awesome. This is basically a mathematical superhero origins story. In 1955, he starts working on using computers to prove stuff. Which we should take a second to appreciate, because this is what computers looked like at the time.

Fig. 5. What the hell is this?

This starts an arms race throughout the 1960's and 1970's for who can use computers to solve the Four Color Problem, and basically everyone is using Heesch's methods. Heesch is close, maybe, but it's a couple of Americans, Appel and Haken, that finally beat him to it in 1976. Their paper is long and basically unreadable, and they themselves admit it:

...50 pages containing text and diagrams, 85 pages filled with almost 2500 additional diagrams, and 400 microfiche pages that contain further diagrams and thousands of individual verifications of claims made in the 24 lemmas in the main section of text. In addition ... certain facts have been verified with the use of about 1200 hours of computer time and would be extremely time-consuming to verify by hand. ... few mathematician have read [the paper] in any detail. 

The upshot is that not a whole lot of people actually understand the proof, and to this day there are those who think that using a computer to prove something is controversial. Some mathematicians are still looking for a non-computer proof, but nobody has succeeded.