The Four Color Map Theorem – Numberphile

The Four Color Map Theorem – Numberphile


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.

Only registered users can comment.

  1. why does he say that the most countries connected to one you can have is 5? what if you had a point, and six points were surrounding it, and the center was connected to all six? isn't that valid?

  2. If the map is such that in any point where more than 2 countries meet an even number of countries meet, you can always colour it with 2 colours.

  3. How about a map on a different surface? 4 colour theorem applies to a plane or a sphere. Or a cylinder, in fact.

    How about a map on the surface of a torus? (I think that's a 7 colour theorem.)

    How about a map on a Moebius band? Klein bottle? Projective plane? Multiple connected tori or projective planes?

    In 3D you can construct a "map" with any number of regions so they all touch each other. So that's just boring…

  4. So you say that no countries can be connected to mor than six whilstl there are plet y with more than six borders

  5. kinda reminds me of the 3 houses with 3 utilities riddle, i wonder if the theorem still applies to a map drawn on a bagel (torus)

  6. 11:06 I'm currently studying Actuarial Science at the University of Illinois (same awesome school as Appel and Haken). You wouldn't think the Four Color Map Theorem would show up in an insurance internship, but I showed this theorem to a few of my coworkers and they made a colorblind-friendly map of the U.S. for me to use in a project. Thank you Numberphile!

  7. I’m no scientist but maybe this can be solved with a bit of game theory:
    >>> Instead of looking at them as networks look at each country as a step on a grid north south east or west. You can color every square in the grid and never repeating a direction until you’ve used them all. As long as the grid is square this will work if your allowed to choose the starting point. Now just substitute directions with the colors and viola. You are bound with maps to 2 dimensions (4 directions) and I think that’s why only four colors is needed. I could be wrong and I don’t feel like devoting brain power to tie at 2 am lol

  8. This video and the problem were quite interesting! But the end was…somewhat unsatisfactory! 🙁

  9. You can color a map with two colors. Countries are green, sea is blue. Most of us smart people know that.

  10. This is bs have a centre country with 6 states 1 centre state with all 5 states touching it. (Imaginary, in real life I am not bothered to look for examples)

  11. Moral of the story, not every mathematical proof is beautiful. In other words, not all theorems have a well understood underlying argument – sometimes they just happen to be true.

  12. Imagine the proof of tree(3) being limited quantity was just provable by checking it out😁😁, humanity would never prove it then

  13. Personally if i was to do a map with multiple counties/states id probably use about 6-7 colors…..

  14. Hi, I want to make friends. I am interested in math, especially in geometry. I found myself alone. No one want to talk with me about math. And I interested not only in math but also in education system and science.

    That was vague, I have nothing to say more. I'm just a little bit sad now.

  15. At 1:48 the maps of the US states contains dark blue, light blue, green, red… and brown. Why is the background (ocean water) ignored? To draw that map 'properly' with only 4 colors you would have to swap CA with NV (so that Nevada was dark blue, CA light blue), and similarly with Ohio and Kentucky. Then the 'oceans/lakes/rivers' can be changed from brown to dark blue.

  16. I have an issue for this:
    Country borders are weird sometimes, and can therefore be split into two or more pieces while still remaining the same country. Take for example Hawaii. Let’s say you put it in the map on the thumbnail. Since it stretches across 4 colors, it would have to be a different color than all of them.

  17. Hi James! Before the four colour theorem, were there maps with 5 colours? If so, do any exist? Thanks

  18. I suspect that this ha to do with reduction of common factors associated with evens and odds or exceeding the number of sides of a triangle or square, your most basic forms. a square could only touch four other colors, but its really only two because if its even number of neighbors, you only need two more colors an it odd, you need three…. 2 is 2, 3 is 3, 4 is 2, 5 is three, 6 is two. and that goes on forever. Do it mathematically, not with diagrams. There is only one scenario where you would need five colors but that scenario does not to my knowledge exist and that would be a three dimensional map where the territories of some countries pass over or under the territories of others in the third dimension. IN that case you would need at least one more additional color.

  19. just put a circle and 5 lines from center to edge. bam! They all neighbor each other in the centerpoint. needs 5 colours.

  20. And technically, I can also color a chess board following the same condition by using only 4 different colors

  21. what if the map is on a ball, 4 shapes surrounding 1 but the 4 shapes all go around the ball and touch on the back, you need 4 colors for the outer 4 and a 5th color for the one that touches the 4 surrounding not sure if the problem is only with 2 dimensions or if it can be mapped in 3d like i stated

  22. Does it count if two sections are connected by a single point. Like two circles connected by a single point, do they count as touching each other or adjacent?

  23. Numberphile: It's possible to paint a map with only four colours.
    Exclaves: I am gonna end this man's entire career

  24. What about portions of land held by a country to which the portion is not connected, or exclaves.
    For example, 3:25 say there is a small country between pink yellow and blue but the country also owns a small sliver of land between yellow blue and purple. Both portions of this country would have to be the same colour to show dominion but together touch all four colour of the wheel, it must therefore be colour five. There are real instances a country being separated by other land masses (eg. Nakhchivan).

    I realise this is pedantic as the problem is supposed to only work with solid land masses.

  25. I took graphic theory in 1989. The math professor told me the same thing. He mentioned unlike other proof, this was done by computer. After 6 months, these two people couldn't find a map that used more than 4 colors. Since no one had time n computing was so expensive, people couldn't check work, so people just believe. The professor got his PhD from Harvard.. he was very knowledgeable. He couldn't do the proof. He just had to believe. We were all laughing in class. The proof happened in 1970s. Its 201miles. Any smart phone computing power is better than the most expensive one in 70s. The super computer in this day can do much more. people still believe without finding real one. Er just believe. This is one theory in my life that we don't a math paper to prove.

    Ok I am not a mathematician. After getting my computer science degree, I don't care about proof anyone

  26. Draw two circles, one bigger than the other, divide that ring into 4 sections + the one on the inside. Inside is connected to all sides, theorem broken?

  27. I wonder what happens when you introduce the concept of an Alaska, ie where a country consists in more than one surface

  28. What a regrettable choice not to mention Gonthier and Werner's work on establishing the correctness (and improving) of the proof.

  29. If you can invent maps, you could do five countries that meet at one point they're all bordering and there are more than 4. I don't know why this is so hard for mathematicians.

  30. What if all the countries were hexagons? Would that not be a case where each country has 6 countries connected to it in a network?

  31. In 1 Dimensoin (a line), you'd logically need TWO colors to color all the segments of a longer straight line. If in a 2 Dimensoins plane you need FOUR colors to separate regions like in this video, would that mean you'd need EIGHT colors to separate a 3 Dimensionnal object in smaller pieces and not have any pieces of the same color touching each other ? Hmmm… (Hope i explained it well enough…)

  32. Wouldnt it be a problem if a country would wrap around itself on a map. looking at the world it is a sphere, so if you would use a map one country will be cut msot of the time. If you would cut it just right it wouldn't be possible.

  33. So I'm looking at this and I'm thinking that in order for a map to require c number of colors, there would have to be a network with n number of nodes such that n=c.

    If some larger map satisfied the requirement where n > c, then there would be nodes that duplicate colors. In such a case there would be a duplicate that could be removed that would reduce that map to one where n=c.

    In order to require c colors, no node can be isolated. That is, every node must be connected to every other node in the map where c=n. If two were not connected, they could be the same color, reducing the number of colors necessary.

    If n=c=3, the network can be represented as a triangle. in order to make a network where n=c=4, a node must be added to the n=c=3 network such that it connects to all three.

    If node 4 is inside the triangle …
    no node 5 added outside the triangle can connect to it.
    a node 5 added inside the triangle that can connect to it must be in one of the sub-triangles formed when node 4 was added
    a node 5 inside one of the sub-triangles is isolated and cannot connect to points outside that sub-triangle, meaning it
    can only connect to 3 out of the 4 nodes and therefore there would not be able to connect to the fourth node and
    force it to be a different color.

    If node 4 is outside the triangle …
    you can connect it to the first 2 nodes without isolating any node
    the third connection between node 4 and the third node in the triangle to be connected must either go left or right around
    the triangle.
    the third connection isolates either node 1 or node 2, leading to essentially the same structure as you would have if node
    4 were inside the triangle (just with a different node isolated)

    If a fifth node can't be connected to all nodes in a 4 node network then no larger network where n=c can exist either. Because if such a network could exist such that all nodes are connected to all other nodes, then removing one node would result in network one smaller where all nodes are connected to each other. Any larger network could remove nodes until it had only 5 nodes where every node were connected. Because the 5 node network where n=c cannot exist, all larger networks can be dismissed.

  34. does it count if the two regions meet at a point, and not a line, for example the four corners in the US, could those be done with only two colors

  35. But if you extend an outer region of the map at 3:26 around to the other side and touch that same color you now have a region that touches pink, yellow, blue, and purple already, so you would need atleast 5 colors. What am I missing here?

  36. wait, if the map is covered with countries all shaped by hexagons, then can you do it with less than 7 colors?

  37. What if some terrorists are discontinuous? Like how Michigan is in half, or how Alaska and Hawaii are USA but aren't connected? One of those, but with more connections? Could they require 5 colors then?

  38. It feels weird but i think i have a 5 sections map wich cannot be coulord with only 4 you need 5 differend types for sure

  39. What if I have this
    |Blue|Red|Green|Purple|
    The a curved territory that curves between the start of blue and end point of purple, maybe I’m breaking a rule or something, could someone explain?

  40. Love the videos, but I imagine split territories throws a wrench in that first statement. You could use different colors for each part, but that would be more confusing I'd imagine.

    It is usual for territories to be contained to one shape, but a map of Michigans could require infinite number of colors.

  41. Here's some logic. try to get all your fingers on one hand to touch each other on a 2-dimentional plane…. you can with 4… not 5… beats the 1400figures QED

    sometimes you have to think inverted, to solve.

  42. What if a country does not have to be uniform? Like Alaska to USA or Kalinigrad for Russia. They are detached regions which you would want to color same way. With this in mind, you can create network that does have crossings in it. And also it makes sense. At least to me. And then it might happen you will need 5 colors.

  43. What about enclaves and exclaves that need to be the same color as their main country? This assumes that countries are solid blocks, which is not true, like the Russian exclave of Kalingrad, the Dutch-Belgian city of Baarle and other examples.

Leave a Reply

Your email address will not be published. Required fields are marked *