So let's talk about the four color theorem! It's a favorite with mathematicians. It's easy to state, so the statement is, every map can be colored using four colors, such that two neighboring countries are different colors. That would be confusing if it wasn't. So all maps can be done in four colors. In other words I'm saying there are no maps that need five colors. It's not obvious, and you'd think more complicated maps would need more colors, but apparently all maps can be done with just four colors or better. So this problem was unsolved for a long time. 125 years, it was unsolved. It was solved finally in the 1970s, although the method they used to solve it was a little controversial at the time, but has had a large effect on mathematics today. So the story of how this problem came around is kind of cute. Apparently there was a guy who was trying to color in the counties of Britain. I don't know why he was trying to do that, but he was, and he suspected he could do it using four colors. And he mentioned it to his brother, and his brother was a Maths student. And his brother mentioned it to his lecturer who was a man called Augustus De Morgan. He's a famous mathematician, and, well, it was De Morgan who spread this problem around. So to prove it, we either need to show that every map can be done with four colors or better, or we just need to find one example that needs five colors. So people were trying it. And if you try it with maps, it does work. If you try it with the map of the world, you can color it with four colors. If you try it with the map of the United States, you can do it with four colors. You can try any real map, you can do it with four colors. I mean you can get this problem to children, right, you want to keep them quiet. After a while, you start to think, "Well, maybe I'll need to invent a map. Maybe if I can invent a weird, complicated map, I can find one that needs five colors." So that's what you start to do -- doesn't look like any sort of real-life map. So we got this map, and now we're going to color it in. So let's start with the middle; I think orange. Next country has to be a different color, so I'm using the purple here. Let's try the next country; so this is all fairly simple -- I can't use purple, I can't use orange, because they're touching -- I'll use the blue. Next one, uh, what do you want, what do you want, Brady? [Brady] Well, we can't use blue or orange...
[Dr. Grime] Mm. [Brady] Oh we could use purple again! [Dr. Grime] Ah, wise. That is a wise choice. Let's use purple again. Why not? Let's not go to the expense of using a fourth color. So now let's do this one. [Brady] We can use blue again. [Dr. Grime] And we can use blue again for that one, excellent. That might put us in a good position when we do the next country. So here we've got -- we can't use blue, we can't use purple; what should we use? [Brady] We can use orange again.
[Dr. Grime] We can use orange, why not? Uh, do you wanna use the orange on the opposite one? So we'll do this one in orange... [Brady] And now we need a fourth color. [Dr. Grime] We do need -- we have to go to the fourth color, do we? Yeah, yeah, yep, purple, blue and orange are being used; this does have to go into the fourth color. I've got pink here. On the opposite side, it's the same, obviously; I'll use pink over here. It looks like we had to use four colors for that. So okay, so this is a map that was solvable with four colors. Here's another important map. I'm gonna make it like that. There's only four countries, but if we try and color it in, Uh, I'll do something similar. I'll do the orange in the middle again, purple up here. Well this one can't be purple; it can't be orange. That means it's blue and this country it can't be orange; it can't be purple; it can't be blue; so I'm forced to use the fourth color which is the pink. So this is an example of a map that definitely needs four colors so we're going to boil the problem down a little bit. Let's say I took this map again -- I'll draw it here. Same map. Instead of coloring in all the sections, let's just say I color in at the center of each region. That'll just get the same idea won't it? I don't have to use all that ink. and maybe instead of drawing out the whole map maybe if I just said if two countries are touching each other, they share a border. Right, I'll just connect them with a line. What I've made is I turn that map into a network so this map has made this network and the question "Can this map be colored using four colors or better?" is the same question of saying "can this network be colored using four colors or better such that two countries that are connected with a line are not the same color?" So it kind of boils down the problem; it makes it more abstract but that's actually a good thing. it makes it easier to solve, there are things we can learn now about maps by studying networks instead. So the reason we want to use networks; for a start, it shows when two maps are the same. I'll show you what I mean. What about if I had a map that looks like this yeah so this this map looks like a handbag as Brady just told me, but if we draw the network for this map, so I'm just going to put a dot in each region and then I'll connect them if they're connected like this. You will find that you get the same network as this previous map we did. So just 4 countries again, it gives me the same network -- it is effectively the same map even though it looks different. So by studying networks we can study all the different kinds of maps even when they look different. Now all maps make networks but not all network are valid maps. I'll show you what I mean this is not going to be a valid map and I'm going to say they're all going to be touching each other. They're all mutually touching countries. They all share borders so it looks like -- if I got this right -- looks like that. Now this is not going to be a valid map, because if you try and turn that into a map it's not going to work. The problem is the lines cross which when you try and turn it into a map doesn't make sense. You can try but it just doesn't make sense. It is allowed if we can untangle the lines and that might happen. i'll show you what i mean so say these are countries here and let's say these countries touch each other as well so i would connect them with a line, but if I do that you see the lines cross. I don't have to do it that way: I could have drawn a line like that. So I could have untangled that. So if I can untangle it that's fine. That's a valid map. And by studying networks there are some features of maps that we can learn by looking at networks, this one in particular. In any map you're going to have a country let's call it A. Country A. Right, there's going to be a country in every map that's either just by itself, like an island, or country A is connected to one other country; that might happen. Or country A is connected to two other countries, so you'll get a network that looks like that. That'd be country A there in the middle, or you might have country A which is connected to three countries, this all seems perfectly reasonable. That's A in the center. Country A could be connected to 4 countries, (now put A in), or country A could be connected to 5 countries. And that all seems reasonable, but every map will have at least one country that looks like one of these. What you can't have is every country connected to six other countries or more. All I'm saying is there is at least one country in that map that's either connected to one, or two, or three, or four, or five. But if you have a map where they're all mutually connected to six or more countries, that's a network that can't be untangled. So all maps have this feature one of the countries is one of these on this list. Now we can start talking about the four color theorem this is actually going to be useful. So the four color theorem is hard to prove and they tried for a long time, like I said it took 125 years. They did manage to prove easier versions of the four color theorem. So the four color theorem means there are no maps that need five colors. I can probably prove that there are no maps that need seven colors. That's probably easier to explain okay. I'm going to have a go. Okay imagine there are maps that need seven colors. These are maps that can't be done with better, right, so there are maps that need seven. Pick the smallest one, okay, so you've got a small one. Now, because it's a map it's going to contain a country which is going to be one of these A's that I've called here on this list. So take that country and pull it out, just delete it, take it away. you've made a smaller map. Now, because it's a smaller map, that means you can do it in six colors. Do you remember, the map I had was the smallest that had to use seven? So if I take a country away, smaller, I can do it with six, great. If I put my country A back in, that means i have a spare color to use for A. I mean the worst case scenario is this last one here. and these could be all different colors. If I put A back in I'm still going to have a spare color, a sixth color that i can use, which shows that the map can be done in six colors after all. Now to show that all maps can be done with five colors -- that's a little bit harder, the proof is exactly the same, the proof is exactly the same except, in this worst-case scenario, down here at the end here um it becomes harder, because if those are five different colors, and you put your country A back in, you might have to reuse a color which you don't want to do. So the argument's a bit more complicated. you have to show that you can recolor it, and you still have a spare color for A. So it's a harder proof but it's along the same lines. Then, they try to do it with four; can we show that all maps can be done with four colors? And that argument doesn't quite work. It just wasn't strong enough. So this went unsolved for a long time. There were some people who thought they'd proved it. They thought they'd actually done it and people accepted the proof, and they thought it was solved for a decade. We thought "Oh! It's done." And then oh! They found a mistake and when actually that doesn't hold up and then "Oh no, it wasn't proved." And we have to go back to square one, we have to find a way to prove this problem. So it took till the 1970s to solve this problem. So the final solution: it was done by two guys, Kenneth Appel and Wolfgang Haken from the University of Illinois. They did it in 1976. It's kind of similar to my proof I mentioned before. They made a list of networks and they said, every map must have at least one of these networks within it. And they showed that every map contains one of these networks. Each one of those networks can be colored with four colors or can be recolored with four colors. And that -- that is enough to show that every map can be done with four colors. Now it is a hard proof and a part of the problem was having to show that this list could be colored with four colors because it was a long list. There were -- how many networks was on this list? 1,938 [sic] networks, and to do that they used a computer. And that was controversial at the time. This was the first computer assisted proof in mathematics. Now it's commonplace and lots of mathematics is done with computers, but this was the first, and people were wary of this proof. For a start, one of the problems is -- it involves checking lots of cases. That's not the best kind of proof. It is a proof and it is valid, but the problem with that is it doesn't give you a deeper understanding of why something is true: just checking lots of cases. Mathematicians not -- do not necessarily like that kind of proof; it's not the best kind. But it's still a valid proof. The proof has been improved for starts, we had this long list of networks that we had to show we could color in. That got shortened. I think it got shortened to some like 1400 and something -- I think it's shorter now. I'm not sure how short it is at the moment. At the moment though the proof still requires this massive checking of cases, so it's still not a beautiful proof. This episode has been brought to you by Squarespace; get ten percent off your first order with them by going to squarespace.com/numberphile. Now I use Squarespace pretty much every day to maintain all sorts of things, from my blog, online store, and all sorts of other websites -- it's a great all in one set up for everything right from buying your domain name at the start through to designing the page itself, I've got all these award-winning templates, they're really good, but you can tweak them as you see fit, of course, and importantly these sites look equally good on computers or mobile devices, it's all taken care of for you, so whatever your next move is online Squarespace is going to make it so much easier and also look much more professional, give them a look. It really doesn't matter what you're doing these days, whether it's just sort of a CV type site or some kind of shop, you really need a classy online presence and that's what you're going to get here, go to squarespace.com/numberphile and check them out. You can even do a free trial before committing and remember to use numberphile to get ten percent off your first purchase squarespace.com/numberphile or you can use the code "numberphile". Thanks to them for supporting this video.
He taught me when I was doing my degree, actually managed to have so many people turn up to lectures that we didn't fit in the room, on a Friday evening!
What about volumetric objects filling 3D space with convex colored regions?
I understand that, for arbitrary 3D maps you could have an infinite color index. For instance, you could fill a room with (up to infinite) layers of different color and extend tubes up and down at different x-y-positions trough all the other layers, touching all of them.
But what about convex shapes in 3D? How many can be made to touch (For both the case of non-convex vacancies in between them being allowed and not being allowed) and how many colors are needed for this?
Is there some sort of generalization to more dimensions?
Maybe I missed it, but he didn't mention that the countries have to be contiguous, did he? I feel like that's important to note, especially since countries like the US aren't.
you had one job
At about 12:45 he talks that this is a special kind of mathematical proof that checks all possibility instead of, I presume, describing within reasonable certainty a certain rule or behaviour if you will (so more like physics perhaps)
So my question, if I'm not wrong about those assumptions, is: What is it called? Those different kinds of proofs, how can I research more about them? This is a bit of a /r/tipofthetongue but I figured it'd be best if I asked in this sub.
I am NOT a math guy, so forgive me if this is off the mark; but can you first of all a) not prove a universal positive and b) very easily create a map that requires more than 4 colors?
Shitty MSPaint aside, it seems like THIS 'map' would need 6 colors no question. (colored). Am I missing something here?
edit: formatting is hard
I just posted a question about rephrasing the problem in terms of graphs here on reddit.
Vertices having different colors implies they are mutually dependent and thus have some (even indirect) connection.
Rephrasing the theorem with colored graphs and regions (interior/exterior with respect to any closed region bound by vertices) seems to give an obvious answer, how does this simple geometric insight fail to prove the theorem?