Hey, everyone. In this lesson,

we will be coloring graphs and we will start with a special case of map coloring.

Assume that I give you the map of continental South America and I ask you to color it

using as few colors as possible such that no pair of neighboring countries share a color.

This is what we typically see on political maps,

neighboring countries assigned different colors.

So, let us first note that Brazil, Bolivia, Paraguay and Argentina

are all neighboring each other.

Which means, they all must be assigned different colors.

So we have to have at least four colors.

And if we can find a good color and we choose to use only four colors, then that's it.

The answer to the problem is four colors is the minimum number.

Let us try to find such a color.

First, we can color Uruguay as either a red or a green,

it doesn't matter because all of its neighbors have already been colored.

Now, let's say we color Chile with blue and then,

maybe blues or red for Peru and blue for Ecuador then green for Columbia.

The remaining countries can be just colored using the red and green.

We did find the coloring which uses only four colors.

Let us try to solve the same problem on the map of The Land of Oz from

the wonderful Wizard of Oz.

Again, there are three countries which are neighboring each other.

So, the number of colors is at least three.

Now, we'll try to find the color in which uses only three colors.

We can color the interior part of the map using only three colors, red, green and blue.

Now, we can color the desert with red and then the remaining part can easily

be colored with green and blue.

So here's the minimum number of colors is just three.

The last problem is to color the Cantons of Switzerland.

Such that, again, no pair of neighboring cantons share a color.

We're going to find four cantons which are neighboring each other so

that the number of colors is, again,

at least four and their exist a valid four colors in the map?

Let us summarize what we did. We colored the map of South America with four colors.

We colored the Land of Oz with three colors.

We also colored Switzerland with four colors.

When they may use more than four colors.

Actually, this is the law of nature.

Appel and Hakkel in 1976 proved that every map can be colored by

using at most four colors.

Here, old maps come with [inaudible].

We actually, assume that all countries are represented with

a different color and we also don't

consider bizarre countries which have infinite perimeter.

But, Otherwise, this is a theorem.

Every map can be colored with only four colors.

What is very interesting and almost unique about the proof of this theorem,

is that it uses computer search.

A reason in it, in 1976,

Appel and Hakel said that if there exist a country checked by a computer for,

then it must be one of these two thousand graphs.

They used computer search to find countries on it thousand hours of computer time.

Later robertson, sanders, seymour and thomas gave a much simpler proof in 1997.