Why is this proof for the four color theorem considered wrong?

Question

I'd like to think I found a proof for the four color theorem, but I also know that it took far smarter people than me a computer simulation to prove. Still, I don't see why this logic should be flawed. If you'd explain to me plainly, I'd love it:

1- You could start with connecting two differently-colored regions holelessly, but adding a hole in the middle allows the other regions to be inside or outside, like this:

Adding multiple holes is also an option, but it amounts to a single hole surrounded by two regions anyway, not really challenging the proof any further.

2a- If the third region is inside, the best case scenario allowing the most amount of possibilities is something like this:

The "best case scenario" here is the one adding as many adjacencies between colors as possible. If even it can't disprove the theorem, it must be true.

3a- Then the fourth differently-colored region must be in one of the gaps. Let it be the top right gap:

4a- Then all the gaps will have 3 colors around them just like in the previous stage, and no progress will be made.

---

2b- If the third region is outside, it's something like this:

3b- To avoid 4a, let the fourth also be outside:

4b- While trying to avoid 4a, we end up with a similar situation to 3b with only 3 exterior regions to surround.

PS. It's based on inductive reasoning. If a fifth color isn't needed during all these steps, it will never be needed after then either, because the holes and outside are just smaller versions of the white areas at the start (hole surrounded by one color or 2 or 3 colors).

Answer 1

In your effort to connect the regions you draw as much as possible immediately, you're actually ending up with maps that are much easier to color than the hardest map! The adjacencies between your regions form an Apollonian network, and it is easy to prove that they are $4$-colorable.

But consider, for example, the problem of coloring all the faces of a dodecahedron. (Technically that's on the sphere, but the four color theorem should still apply: just poke a hole in the sphere and stretch it out like a balloon, and you get a planar map.)

• Your maps all have an obvious weak point: a region that only borders three other regions. Such a region can always be colored in at the end, once everything else has been colored.
• The dodecahedron has no such weak point. If I color any $11$ of the regions and forget about it, then when I get to the $12^{\text{th}}$, it could end up having all four colors next to it!

In fact, you're coloring regions as they appear, which is a much harder problem: it's called an "online" coloring problem. In the case of online coloring, the analog of the $4$-color theorem is false! (That's another reason why we know your proof is insufficiently general: if it were, it would prove the stronger, false result.) If I get to draw regions one at a time and ask you to color them, then I can draw a map on which you'll eventually fail.

How would I do that? I would begin by drawing two regions that are not adjacent at all, and then decide what to do next depending on what colors you give them:

• If you give them the same color, then I can draw four more regions that are all adjacent to each other, and each is adjacent to one of the first two regions (as in the first image below). Those will need four different colors on their own, but then they will conflict with the first color you used.
• If you give them different colors, then I can draw three more regions that are all adjacent to each other and the first two (as in the second image below). Now all five regions need different colors.

Of course both of these maps are $4$-colorable, if we reason about the colors in advance. But this requires more sophisticated logic.