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

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

• I don't think this should be downvoted; But giving an answer is made harder by the fact that there are no counter-examples :) Commented Feb 11, 2022 at 10:58
• Everytime the phrase "the best scenario is..." is used in a proof without explaining exactly what it means a thousand alarm bells should go off. Because trying to explain exactly what that means usually hides the missing difficulty. Commented Feb 11, 2022 at 11:11
• Even if everything you say is true and can be made formal (which I doubt, see the comment from Michal Adamaszek), how does this prove the theorem? As far as I can tell, you have only considered maps with at most four regions. How do you color an arbitrary map? Also, what if the "best case scenario" in 1 does not occur? What if, at any point, there is no region left that fits your description? For example in 2b, what if there is no region on the "outside" (for more complicated regions, it might not even be clear what that is) that connects blue and red? Commented Feb 11, 2022 at 11:27
• @MichalAdamaszek 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). Commented Feb 11, 2022 at 12:33
• In 3a you are assuming that if the top right gap needs a fourth colour, then it must be because of a region that touches all three parts of the boundary. This is not the case. There can be many reasons for a fourth colour - there could be a triangle region at the top corner touching red and blue, surrounded by a band that also touches the red and blue. One of those must be green even though neither touches the yellow band in the centre. And the choice of which is yellow and which is green can depend in some complicated way on the regions between them and the centre yellow band. Commented Feb 11, 2022 at 13:09

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.