Four Color Theorem, So Easy?

Why it needs at most four colors to draw a map?

  • Because you can not put a fifth color adjacent to four colors on a map!

Let’s say there is a unlimited plane and the only one color.

A

When add every new color, remember it should adjacent to all the other colors. In this way, we could find the biggest number of colors to draw a map.

A | B

The third color adjacent to A and B, so it is at the center line.

   |
A /  \\
  | C |
  \\  / B
    |

The fourth color adjacent to A, B and C, so it is at the one of the two points.

    |
A /  \\
  | D |
    一 
  | C |
  \\  / B
    |

The fifth color adjacent to A, B, C and D. But you can not find a area to place E…

Riemann Hypothesis? Easy! I do not know what the fuss is. You simply cannot put a non-trivial zero outside of the Re(z)=1/2 line!

facepalm

11 Likes

@ _Norvig ​ :

How many colors does a 5-cycle need?

(There are 5 regions ​ - ​ g0 , g1 , g2 - g3 , g4 ​ - ​ and their
adjacencies are as indicated by the segments in the above image.)

1 Like

Ehhh…

It’s cute, but no, this isn’t easy.

Your mistake is of the form “oh, this seems like an easy problem, let me draw an example. See, my example only needs four colours, so you need at most four colours”

The part that’s missing is showing that your example is exhaustive, that is, that there does not exist a different map that cannot be coloured with four colours.


The point is, if the theorem is true, then it is indeed impossible to come up with a map that has five countries all sharing a border with each other.

But, just because it’s difficult to create such a map, does not mean that it’s impossible to create it. This is the part that requires a proof (and as far as we are aware, such a proof cannot be written down in a paper with less than a double-digit number of pages written in a language only trained mathematicians in the relevant field can understand)

On the opposite end, if the theorem is false, all you have to do is create a map showing five countries all sharing a border. (it happens to be impossible, but that’s kind of what you have to show).

5 Likes

3

1 Like

Should be called the “three colour theorem” then

1 Like

image

Real trivial problem

4 Likes

Isn’t the four color theorem just about that simple if restricted to five countries? I assume the difficulties come in when there are more.

The five color theorem on the other hand is one with a nice simple proof that’s just a few steps harder than “see, it doesn’t work”.

3 Likes

So, let me give a nice thing you could(n’t) prove.

Let me say that a sequence of symbols repeats N times at the end if it ends with a repetition of the same symbols for N times (and no more than that).

For example, the word “goo” has a repetition of 2 times the symbol “o”. The word “receded” also has a repetition of 2 times, with the part “ed” appearing twice at the end. Finally “train” only has a score of 1, since there is no repetition at the end.

Let’s now make a sequence, where the next number is simply the previous number and the repetition at the end glued together:

1 (has 1 repetition at the end, so:
11 (has 2 repetitions at the end, hence:)
112 (has 1 repetition at the end, therefore:)
1121
11211
112112 (has 2 repetitions of “112”, thus:)
1121122
11211222
112112223
1121122231
11211222311
etc.

If you feel like it, you can check if this sequence will ever contain the digit 4, and with some effort, you might find it within an hour of work or so using pencil and paper.

The challenge is to show whether the number 5 ever appears. I’ll assure you that you won’t find the answer by just trying it out.

Spoiler

The position where 5 first appears is at a number with 1023 many digits. Note that the total number of atoms in the universe has about 80 digits…

Even more interesting, if we invent a new symbol for each natural number, to avoid the ambiguity of “10” consisting of two symbols, then every (symbol for a) natural number will occur at some point: the sequence is unbounded.

3 Likes

I also recommend the book Four Colors Suffice by Robin Wilson.

https://books.google.ie/books/about/Four_Colors_Suffice.html

^google preview.

I saw him give a talk on the problem, and it was interesting enough for me to buy the book and I enjoyed reading it :slight_smile:

Naturally if you can get it printed in colour that’d be useful :slight_smile:

There was a funny discussion of how older editions weren’t printed in color, and so used different dotting and shading and so on for colors.

1 Like

Your idea is a good starting point, but not a proof. If you were thinking of your argument as a proof, then the falasy is basically (in my interpretation) the following: You are aware that maps can have many countries, but you argue that it suffices to look at local parts of the map, i.e. consisting of at most 5 countries. However, as @hoctaph s example shows, local properties do not necessarily extend globally: Any odd cycle of a graph is locally 2-colourable, but as a whole you need 3 colours.

In terms of graph theory, the 4-colour theorem can be stated as “Every planar graph is 4-colourable.”

In this context, your argument is basically “The complete graph on 5 vertices (= K5) is not planar and not 4-colourable, thus every planar graph is 4 colourable”.

However to make this argument complete, we would need to argue the following additional step: “Assuming a graph is planar and not 4-colourable, then it contains the K5 as subgraph”.

In short: Your argument is incomplete.

5 Likes

I think the 8th term in that sequence should be

11211222

1 Like

Yep, fixed

might as well just go on till you hit 5