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