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

you failed in the first example.. orange on two sides..

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

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.

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.

I've won. I made a map that needs 5 colours. Where can i collect my money?

Happy Birthday to Wolfgang Haken!

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.

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

What about with Enclaves and Exclaves? Russia, any one?

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.

Aaand it all breaks when you try to color countries on a globe.

angrily huffs at my map where sudan and south sudan are the same colourWhat about like a pint between 5? Like a pizza almost

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

Pretty sure I just drew one that needs 5

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

This entire video is defeated by exclaves.

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

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?

Numberphile: It's possible to paint a map with only four colours.

Exclaves:

I am gonna end this man's entire careerA triangular tiling has 6 edges from each vertex.

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.

india v bangladesh border will be the ultimate test

How can I check if my map is true or not? I made one and every single combination I have tried it needs 5.

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

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?

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

"1970's, final solution."

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

Colourblind people can't see the point for this theorem.

my globe has 6 different colors

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.

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?

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…)

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.

Graphs, not networks T-T

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.

IS ANYONE ELSE PISSED OFF AT THE PURPLE SEGMENT IN THE LAST SLIDE

What if countries could be 3D. Would 9 colours suffice?

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

Curious to see how many you would need in 3 dimensions

I love this mans enthusiasm

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?

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

Anyone else see the person standing in the window?

I created a map that needs 5 colors

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?

The key to breaking this:

Enclaves and exclaves

Wait until he finds out about enclaves.

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

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?

hey what if Oklahoma's panhandle was a seperate state

i just made a map that needs five colors

~~A world map could need 5 colours if you colour the seas as well.~~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.

What rivers though? all the geographic regions but then there's the rivers & oceans and lakes

This is only true if you don't count countries that have disconnected parts.

You look like projared, bill nye, and Reportoftheweek fused together and you were the result

Real maps might not because of enclaves and exclaves.

Here's a proof. try to get all your fingers on one hand to touch each other… you can with 4… not 5… Done

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.

This falls apart when countries have exclaves and enclaves

What if you do the world, but count the oceans as one tile

France is the same color as germany

Does this work for non-contiguous territories?

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.

It hurts me that Michigan was colored two separate colors in the beginning

What if one country was next to four other countries???

Enclaves and exclaves kinda mess this up though, but if we lived in an ideal world then this would work

You can actually color any map with 3 colors. Just don't color all the territories.

what about exclaves and enclaves?

What about enclaves and exclaves

Does is hold true for coloring a globe?

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.

what about 3d maps? in 1d map its 2 colour, 2d 4, 3d would require more?

6:03 careful dude you're gonna summon the devil

Is it just me or is a map with 5 easy

Theoretically, if a state were to be under the same name but in separate chunks such as Michigan, would you color them the same color as they are the same state?

It seems like this has to do with the fact that the maps are drawn on a flat piece of paper. If you draw a map on a torus, you can force the need for a 5th color.

12:30 mathematicians don’t like the real world

You forgot about country exclaves

Inclave and exclave

I imagine people scribbling on a piece of paper then trying to color each closed off section with only four

1:45 Now take that, and look. There's a fifth color: Brown. Add in the uncolored space as another part of the map needing a color. I count all four colors in contact with that.

This was a problem in my school

Thanks 🙂 I’m gonna get a free slice of pizza!

When you have a fictitious world with strange exlaves you must use more than 4 , if you want the exclaves to match the color of the mainland.

i'm pretty sure the Irish don't consider themselves counties of Britain lol

1:49 Arizona and Colorado touch and are same color

The map of the world most certainly has 5 mutually bordering countries, due to enclaves and exclaves. So no, the map of the world is not colorable by four colors such that every bordering COUNTRY gets a different color, as stated in the video. COUNTRIES are not contiguous regions in real life.

Well… ships count as foreign ground… the practical way of solving it…

Ever since the computer solved this problem the computer has been trying to "SOLVE" the colour problems with our real maps…..one day there will be zero difference between any of us because the "problem" of humanity will of been solved by computers……

So if you take a map like he has in 3:56 and put a country around it with a section of that country nested in side the inside circle you need five colors don't you? It be like how Russia or the US isn't all self contained but it's colored the same because it's the same place politically

Tyro question: does not this subject have correlations in topology?

Actually I my maths teacher told us to sit for 3 hours in class trying to design a map that needs 5 colors. I did manage to do one, with 12 over regions. However, one person in my class did it with only 5 regions…

exclaves create a problem

is it just me or is it really easy to draw a map that needs 5 colours. If you had 4 enclaved countrys (a country within another country) all touching that would need 5 colours right?

Awesome explanation.

A map is only a 2D surface. How many colors would we need if we brought this into the Third Dimension and why?

If a country can be split up like the USA and still require the same colour then you aboslutely need 5 colours.

This is an excellent, clear presentation by Dr. Grime.