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