- This episode is supported by Skillshare.
Hi guys, Jade here.
Today, I wanted to talk about a really interesting problem
called the four color map theorem.
It's really cool because it was the first page
of theorem to be proven with the help of a computer.
It caused a lot of controversy
because basically no one could understand it.
This raised a lot of questions about the nature
of mathematics and what really counts as a proof.
It also shines a big, uncomfortable light
on the limits we may have as humans
and asks whether computers may be necessary
for the future of mathematics.
The story has it that in 1852,
a mathematician named Francis Guthrie
with coloring the maps of counties of England.
Don't ask me why, but anyway, he noticed
that he only needed to use four colors
so that no two touching counties with the same color
he wondered whether this was the case with all maps.
And if so, what was the reason?
H he sent a message to his brother Frederick,
also a mathematician.
He told him about his full color map theorem,
and wondered if it was a known thing.
And if so, why?
Little did he know
that his questions would go unanswered
for over a hundred years.
What's interesting is
that the question itself is pretty straightforward.
So it seems odd
that the solution would be so complicated.
To understand why,
let's first try to prove an easier problem,
the five color theorem.
It's pretty much exactly the same as the four color theorem
just with five colors.
Formally it states,
"Given a plane separated into regions,
the regions may be colored using no more than five colors
in such a way that no two adjacent regions
receive the same color."
So when proving a theorem, three techniques
that mathematicians often use are induction, contradiction,
and invariance.
Luckily for us, this proof involves all three.
So let's briefly go through what they all mean
before we start.
Proof by induction is just showing
that as long as you can take the first step,
you can take every step after that.
Say, you want to prove
that you can climb to the top of this ladder.
There are only two things you need to do.
One, prove you can get on the first rung,
and two, prove that you can get to the next one
from whatever rung you're on.
Then it follows that if your proof holds for any step, n,
it'll hold for any step, n+1.
So no matter where the top is, you'll eventually get there.
Then there's proof by contradiction.
This is a fun one.
A couple of weeks ago, I made a video
about one of the most fascinating proofs by contradiction,
the halting problem.
But briefly, instead of directly proving the thing
you're trying to prove,
you assume the opposite is true
and show that it results in a contradiction.
For example, if you wanted to prove
that there is no biggest number,
assume that the opposite is true,
that there is the biggest number.
Let's call it a bajillion jillion.
Let's say a friend John comes along with the question,
what about a bajillion jillion plus one?
So you claimed that a bajillion jillion
is greater than a bajillion jillion plus one,
but if we minus a bajillion jillion from both sides,
we're left with zero is greater than one,
which is a contradiction.
This argument could be used for any number.
Therefore, no biggest number exists.
The third technique is invariance.
An invariant is the property that stays the same
even when other things in your system change.
For example, in Euclidean geometry,
the angles of a triangle always add up to 180 degrees.
You can do whatever you like to the lengths
of the sides or the angles within the triangle,
but the 180 degree rule never changes.
It's invariant.
Cool. So equipped with these three tools
of mathematical deduction,
let's make a start on this proof.
Proof that you only need five colors to color any map
so that no two countries sharing a border
are the same color.
This is gonna be fun.
So the first step when solving any mathematical problem
is to get rid of any unnecessary information.
There's a lot of unnecessary information.
We don't care that Italy is shaped like a boot
or that Paris is the capital of France.
- [Willie] Whoa, someone doesn't care
about basic geography.
I'm not aware of this concept.
What's going on here?
- [Jade] Guys, this is my friend
Willie from the YouTube channel KhAnubis.
He's pretty obsessed with geography.
And he's made a video
about maps too, which I've linked in the description.
Now, Willie, I'm not saying that I really don't care
about what the capital France is,
even though I kind of don't,
it just makes this problem easier for us to solve.
- [Willie] Okay, if it makes the calculations easier,
I'll let it slide.
- Cool as I was saying, we only care about two things,
how many countries and the borders that connect them.
So let's transform this map into what's called a graph.
We can replace all the countries with dots or vertices,
as they say, and all the borders with lines
that we're going to call edges.
When the edges and vertices form a closed loop
this is called a face.
We may as well talk like graph theorists
if we're going to be proving one of the hardest theorems
in graph theory, this is what's called a planar graph,
meaning that you can draw it on a piece of paper
without any of the edges crossing each other.
This is going to be important later.
So now if we can color all the vertices
of a planar graph using only five colors
so that no two vertices sharing an edge are the same color,
we've solved the five color theorem.
This is exactly the same model as the map from before,
just in a nice, neat little package of dots and lines,
and no delicious baguettes or pizza to distract us.
So it's time to break out our first tool, induction.
Proving that every graph is five colorable
is pretty ambitious,
but the first step of induction is simply showing
that you can get on the ladder.
In our case, that would be showing that graphs
with one vertex can be colored using five colors.
Alright, well, that's step one, done.
Step two, prove that whatever rung you're on,
you can always get to the next one.
So in our case, that would be assuming
that a graph with n amount of vertices is five colorable.
Prove that a graph with n+1 number of vertices
is still five colorable.
Step two is a bit harder than step one.
So here's a graph,
and let's say it has n+1 one number of vertices.
It doesn't matter about the actual number of vertices,
since the rule is supposed to apply to any graph.
If we go back to the ladder analogy,
it's just like saying it doesn't matter what rung you're on,
as long as you show you can get to the next one.
So now, if we assume that graphs that have n number
of vertices are five colorable,
let's show we can make the jump to graphs of n+1 vertices,
if we remove a vertex from this breadth,
it becomes a graph with n vertices, right?
And we assumed that graphs with n vertices
can be colored with just five colors.
So now let's see if we can call it this graph
in such a way that when we add the vertex back,
it's still five colorable.
Then we'll have proven that if a graph with n vertices
is colorable, we can always make the jump to n+1.
But how can we make sure that we can add a fifth color?
It'd be good if we could find a vertex with four neighbors,
then we'd be guaranteed to have a fifth color free.
Unfortunately, some graphs have a vertex
with just four neighbors,
but we're going to show in a bit
that all graphs have have a vertex with five neighbors,
and that's good enough.
This one has five.
So let's take it out.
The remaining graph with n number of vertices
is five colorable, according to our assumption.
Now here comes a fiddly part,
so pay close attention.
We're going to be dealing with the five neighbors,
our removed vertex was connected to.
Let's call it, V.
We'll number them in a cyclic manner,
one, two, three, four, five.
Right now all the numbered vertices
are taking up all five colors, green, red,
yellow, blue, and purple.
And so we can't bring our removed vertex, V, back,
without breaking the five color theorem.
We've got to somehow arrange them
so that they only take out four colors.
To do this, let's look at one and three,
and highlight all the vertices the the same color
as them, green and yellow.
We can say that vertex one isn't connected
to any yellows, so we can change it to yellow.
Now, will the neighbors only take up four colors
without breaking the rule.
So we can bring back our move to node V
and give it the fifth color.
This graph, n+1 is still five colorable.
Case closed but not really, this one always works.
Take this graph, for example.
It's the same one as before
but some of the colors have swapped around.
So let's try the same trick as before.
Highlight one and three and mock all the vertices
with those colors.
But now when we try the old swapper rule here,
we find we can't get rid of any colors
without having two connected vertices the same color.
This is because we have this path of yellows and greens
from vertex one to three
that we didn't have in our last example.
So was the mighty five color theorem broken then?
Not quite.
Let's look at vertices two and four,
one and three form a path, blocking two and four
from connecting.
So I can just play the old swapper rule
with one of them instead.
Again, the five vertices only take up four colors.
So we can bring back that Vee and color it in
with a fifth color.
And the five color theorem is saved.
You will always be able to do this
with any vertex that has five or less neighbors.
So how do we know we can always find such a vertex?
Well, now it's time
for our last proof technique, invariance.
Let's bring in an invariant called the Euler characteristic.
The Euler characteristic is a rule
that for every connected planar graph,
the number of vertices minus the number of edges,
plus the number of faces is always equal to two.
If we start with a vertex on the outer face,
we have one vertex and one face.
We can do two things to build upon our graph,
add another vertex and connect them by an edge,
or connect to existing vertices with an edge.
As you can see, no matter how big we built out graph,
the Euler characteristic will always equal two.
So equipped with our invariant,
let's try out the
one remaining proof technique, contradiction.
Let's assume that, in fact,
every vertex needs to have a minimum of six neighbors
and there can't be any with five or less.
There needs to be at least three times the number
of edges as vertices,
because every edge is shared between two vertices.
Now we go to try and prove that this assumption
results in a contradiction.
Let's go back to Euler's characteristic for our sake.
Every face is made of at least three edges, right?
And every edge is shared between two faces.
Remember we count the outer face too.
So then the number of faces is less than
or equal to two-thirds the number of edges.
So if we plug this inequality into Euler's characteristic,
we get that the number of vertices minus edges,
plus two-thirds the number of edges
is greater than or equal to two.
If we simplify, multiply by three, and re-arrange,
we get that, the number of edges is less than
or equal to three times the number of vertices minus six.
Alright, now let's compare this with our assumption.
The term e minus three V on the left is the same.
So we can write these two equations as one inequality.
So then we get that the number of edges,
minus three times the number of vertices must be smaller
than minus six from our theorem,
but must be greater than zero from our assumption.
This is a contradiction.
Therefore, our assumption that the minimum number
of neighbors is six, is wrong.
The vertex with the minimum number of neighbors
is five or less.
So that means out proof by induction is safe.
So to recap, we used proof by induction
to show that if a graph with n number of vertices
is five colorable,
a graph of n+1 is also five colorable.
Therefore, any planar graph can be five colorable.
However, this is only possible
if there is always at least one vertex
with five neighbors or less.
We've proved that
by assuming that the opposite was true
and showing that it contradicts
with the Euler's characteristic.
And because the vertices, edges,
and faces will all just stand in
for countries and their borders.
We proved that? Yes.
Any map can be colored using only five colors
with no two adjacent countries being the same color.
So the five color theorem is true. Great.
So we can finally answer Guthrie's question.
Oh, wait, no we can't.
He's four colors.
But can we extend out proof to four colors then?
Well, the reason this proof worked so well
is because of the fact
that we can always find a vertex
with five or less neighbors.
But this doesn't help us for the full color case.
We need four neighbors or less, which we can't guarantee.
The four color proof actually went unsolved
for over a hundred years,
until two mathematicians Appel and Hakan,
announced that they'd at last found a proof.
The only problem was no one could understand it,
not even them.
This is where the computer comes into the story.
I won't go into the full details of the proof
because their paper was 60 pages long.
But basically, I imagine that graphs is separated
into two categories, ones that can be covered
with four colors on less and ones that need five colors.
We already showed
that all maps need a minimum of five colors.
And it's obvious
that some maps can be colored with just four colors.
So what Appel and Hakan needed to do
was show that all graphs exist on this side of the line.
They did this by proof of contradiction.
They needed to show
that all graphs have a certain property guaranteeing
that you can reduce them in size
without ever crossing this line.
Basically it means, if they start with five colors,
you can always make the number of vertices smaller
while still needing five colors.
But of course, if you keep making the graph smaller,
you'll eventually end up with a graph
with four or less vertices and therefore four colorable,
which would be on this side of the line.
So that means that if all these graphs did in fact
have this special property of reducibility,
they would all have to have started
on this side of the line.
The hard part was proving
that old graphs on the five color side,
do indeed have this special property.
The strategy that they used was to share that every graph
on this side of the line would have to contain one
of 2000 configurations, guaranteeing the property.
Checking them by hand would have been very time consuming.
It would have taken months
if not years of time spent tediously coloring in graphs.
They needed a computer to do it.
And after over a thousand hours of computation,
we finally had our answer, that yes,
all graphs on the five color side
did have this special property,
meaning they simply couldn't exist
without inducing a contradiction.
All maps are in indeed four colorable.
So they have it Guthrie.
There's your answer.
But this feels very different
to the proof of the five color theorem.
We don't really know why it works.
The computer could have just as easily returned a no,
and we wouldn't have learned anything different.
The mathematics community had a lot
of trouble accepting this as a proof.
The mathematician Paul Halmas said,
"I do not find it easy to say
what we have learned from all that."
And Daniel Cohen said,
"The mission of mathematics is understanding.
Admitting these computer shenanigans
to the ranks of mathematics
would only leave us intellectually unfulfilled."
As you have to admit, they're kind of right,
but this raises some very interesting questions
about the nature of mathematics.
Who judges whether or not something is a proof?
Are we being arrogant and assuming
that mass should abide by human understanding?
Kenneth Appel said,
"The computer was much more successful
because it was not thinking like a mathematician."
Since then many more mathematical proofs
have been provided by computers.
Recently, the Boolean Pythagorean triples problem
was solved by a computer,
running for four years, generating a 200 terabyte proof
which was later compressed to 68 gigabytes.
Just enough for a lifetime of reading.
This problem started off with someone coloring in maps
but we spent the whole time talking about graphs.
That's because all of the information we needed
was captured much more effectively in a graph.
Different representations can be useful
for different things.
My friend Willie has made a video all about it.
Willie, why don't you give us the lowdown?
- [Willie] Thanks Jade.
Wait, hang on.
I don't think I can animate myself like this, one second.
(percussion sounds)
Yeah, that works.
Now, I've always been into maps and geography
but one important thing to realize about
just about all maps is that they're all lying to you
in some way or another.
Even the most accurate honest maps are hiding,
exaggerating, or misrepresenting something on it.
But this is actually so that they could do a better job
at showing what they're actually trying to show you.
This is why even the most well-designed Metro maps
are terrible as walking guides.
If you're interested since this video was made
as part of the collaboration,
head over to my channel, KhAnubis, to find out more.
- I've linked to that video in the description.
So make sure to check it out right after this.
The four color map theorem would never have been solved
if it wasn't for the clever methods
of thinking as humans have developed
as a way to tackle problems.
If you'd like to practice some of these skills yourself
and get better at problem solving skill,
Skillshare.com is an interactive learning website
where you can build your logic and reasoning skills
through the thousands of courses they offer.
There are plenty on science, technology, programming,
and basic problem solving,
like how to solve a Rubik's cube,
how to work out percentages,
and an entire course on discrete mathematics.
There are also plenty of basic life skill courses,
like how to make Sushi,
and an entire course on how to an extension cord.
Skillshare is offering a special promotion to my viewers
where you can get the first two months totally free.
To sign up, just use the link on screen
which I've also put in the description.
Thanks for watching guys.
So you may have noticed that this video was a bit longer
and more in-depth than my usual videos,
and that's because a few weeks ago I posted a poll
in the YouTube Community tab,
asking whether you guys did want more in-depth videos.
And the majority of you said, yes.
So let me know what you thought about this video.
Was it in-depth enough?
Was it too in-depth?
I hope it was in-depth enough
because I don't think
I could make more in-depth videos than this.
But guys, any way, feedback is always appreciated.
That's it for me. Bye.
(upbeat music)