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.