The Five Color Theorem (without Kempe chains)

Proofs:

The degree of a vertex or a face is the number of edge incidences (edges that meet a vertex or face twice are counted twice). Each edge has two vertex incidences and two face incidences, so both the sum of vertex degrees and the sum of face degrees equals 2E.

Eliminating "bad borders" means that each vertex has degree at least 3 (unless there are just two faces). Then, the sum of degrees is at least 3V, and hence 3V ≤ 2E. Plugging that into Euler's formula to eliminate V yields the inequality E ≤ 3F-6 (when F ≥ 3).

You can't have a neighborly map of six countries because you would need 6 choose 2 = 15 borders, but 3(6)-6 = 12. The average degree of the faces is 2E/F ≤ 6 - 12/F, which is less than 6.

Errata:

Whoops, looks like Franklin's paper was actually from 1934, sorry!

[Timothy-Sun]

I forgot to mention in the video that the proofs of the claims in the flowchart at 7:56 are sketched out in the video description. Hope this helps!

[toricon]

Considering proofs as algorithms, and vice-versa, is one of my favorite mathematical techniques. It actually has the fancy name of "the Curry-Howard correspondence" and has given rise to many fascinating things which this margin is too small to contain.

[username]

Really wasn't expecting this to be the first video of the channel, looks so professional, nice job. Of course, the great manim helps.

[bonbonpony]

This might be the first English video that I had to watch with subtitles turned on, because I couldn't understand a word out of this muttering :q

[johnchessant]

Great video! I hoped to see something like this for a while because the topic lends itself nicely to an animated video, and you did an awesome job with it.

[tfae]

Thank you for the video! I've been working on formalizing the five color theorem in Lean. I'm using the Kainen 1974 paper that you referenced in the video. It was refreshing to see another take on the topic.

[theanamex]

Great video for 1m+ YouTube channel. Can't believe you're just starting out. Superb.

[cmilkau]

Interesting, two nice proofs of the 5 color theorem I didn't know! We actually learned a third proof that found minors K5 or K3, 3 when more colours are needed, and as these can't be drawn on the sphere, it means you never need more colours on the sphere.

[mstmar]

for the 3rd challenge, you can need infinitely high number of colors. we can recursively create a map that needs n colors by appending n-1 smaller maps (each needing a different number of colors) to a new region. If we only append to the top edge, we get an exposed edge to the highest color at the bottom, which we can use to connect to the following maps. at 2^(n-1) regions for n colors. i'ts not optimal in the number of boxes, but we know it exists. coloring this map top down will require an extra color. funny part is that this construction makes trees which should be 2 colorable

e.g.
1: trivial
1


2: also trivial, but using the recursive function: add the 1 map created above to the top of a new region
1
2

3: add the 2 maps above, side by side but not touching to the top of a new region
1
2 1
333

4: add the 3 above to a new region
1
2 1 1
333 2 1


...

[EebstertheGreat]

BTW, there is a great paper discussing the minutiae about what types of countries are allowed and what counts as "sharing a border." The four-color theorem is often described in terms of political maps, but the only condition usually imposed is that all the territories in the map are contiguous (i.e. path-connected), and that two territories "border each other" iff they share an uncountable number of points (e.g. an entire line segment or curve). If we want to be precise, we need a stronger condition. It is not sufficient that our territories are bounded by Jordan curves. These boundaries need additional properties such as being rectifiable for the four-color theorem to be true.

I'm having a hell of a time trying to find an old pdf I used to reference to make this point. I'm sure it's still out there. The idea is that you could make four (or any finite number of) territories share a single line segment as a boundary by making their boundaries infinitely long. They essentially get alternating rectangles of decreasing thickness closer and closer to the shared boundary, so that every point in the line segment is a limit point of every territory. Each territory is path-connected in the usual topology of R², yet all _n_ of them share a common border. Avoiding this sort of edge case requires a more careful formulation in what shape the territories may take, e.g. limiting them to having rectifiable boundaries. This might seem unsatisfactory though, since real territories do not have rectifiable boundaries in the mathematically ideal case. Basically, we just want the connectivity graph to be planar, but exactly what that means in terms of our map is more complicated than one might expect.

[andreiignatov]

Great video. It was really interesting, well crafted, and you have a pleasant voice!

[jonaw.]

I'm not sure I understood most of it, but the graphics really helped visualise what you were talking about. I've definitely much to learn still

[layt]

Very good video. Your explanations break down the concepts enough for most people to understand them but you still keep them short and concise. Adittionally your examples and visuals are extremely helpful.

[carlossancheslopez]

I can't believe this is your first video on the channel with this quality. Keep it up

[punditgi]

One of the best videos I've ever seen. Bravo, monsieur! 👍

[engineerbill]

dude! This is a dope video
well done, very pog :)

[Fanny-Fanny]

Bloody brilliant! New sub here. I'll be seeing you when you hit 100k and beyond (and well deserved it will be). Bravo!

[luminica_]

We can create a map such that The Greedy Algorithm can use an arbitrary large number of colors.
Let's start with a region in the map. Color it.
This set of regions (only 1) will be a1.
We create another region and place a1 inside it, it has to use the color 2 since it is bordering a1. We call this set of regions a2.
We create another region and place a1 and a2 inside it, it has to use the color 3. We call this set of regions a3.
We can use this process to go arbitrarily large in numbers.

[霍金本人]

Feedback:
This video gives really good introduction to map coloring algorithm from the point of view of computer science.

Further reading:
You may be interested in reading some more materials in graph theory topics, for example:
1) R. J. Wilson, Introduction to Graph Theory;
2) D. B. West, Introduction to Graph Theory; J. Clark; and
3) D. A. Holtan, A first look at graph theory.
These may prove some solid graph theory background for related computer science topics like TSP or Chinese Postman Problem, and also some mathematical idea behind interesting algorithms like Dijkstra algorithm and Kruskal algorithm.

[zl]

The answer to challenge 2 is yes:
Take any optimal coloring C. First greedy color every region that has a 1 in C. Since they have the same color in the optimal coloring, they none of them can be neighbors, so they're each colored 1 in the greedy coloring. Next color every region that has a 2 in C. Since none of them are neighbors and the largest color we've used is 1, each receives color at most 2. By induction, each region receives color less than or equal to its color in C, so the greedy coloring uses at most as many colors as optimal coloring C, i.e. is optimal