42
$\begingroup$

My brother in law and I were discussing the four color theorem; neither of us are huge math geeks, but we both like a challenge, and tonight we were discussing the four color theorem and if there were a way to disprove it.

After some time scribbling on the back of an envelope and about an hour of trial-and-error attempts in Sumopaint, I can't seem to come up with a pattern that only uses four colors for this "map". Can anyone find a way (algorithmically or via trial and error) to color it so it fits the four color theorem?

"five color" graph

$\endgroup$
  • 78
    $\begingroup$ They call it the Four Color Theorem for a reason – you can't disprove it. $\endgroup$ – Gerry Myerson Nov 2 '16 at 6:31
  • 29
    $\begingroup$ @GerryMyerson Right, because no proof of a theorem, especially one with such a controversial history using the one of the most controversial proof techniques in all of mathematics, has ever been wrong. $\endgroup$ – sloth Nov 2 '16 at 7:29
  • 16
    $\begingroup$ @sloth, how much would you like to bet that the Four Color Theorem isn't wrong? $\endgroup$ – Gerry Myerson Nov 2 '16 at 8:01
  • 41
    $\begingroup$ @sloth the computerised check of the four-colour system may have been controversial when it was published, as it was just some program that could well have had bugs in it. But it has since been backed up by a dependently-typed proof system. You can't get any more certain than that about any proof. $\endgroup$ – leftaroundabout Nov 2 '16 at 10:53
  • 24
    $\begingroup$ The rule of thumb is to always assume that you are the one missing something. You should never say "a possible disproof" (or rather "counterexample"), but rather "What am I missing here? I am probably wrong." Sure, people have made mistakes in the past. People have claimed to have proved something, only years later to learn of subtle mistakes that they have made. But courtesy to the rest of the mathematical community dictates that you should generally assume that the fault lies in your understanding, rather than with everyone else. Which is why your post has come under fire here. $\endgroup$ – Asaf Karagila Nov 3 '16 at 9:27
113
$\begingroup$

Starting at the top, going clockwise:

  • center: 1, 2, 3
  • middle: 2,4,3,4,2,4
  • outside: 1

4colors

I hope this helps $\ddot\smile$

$\endgroup$
  • 5
    $\begingroup$ Accepting this one because it was first, and works. I knew my brother-in-law and I couldn't have broken something like this in a one hour brainstorming session at 2am, LOL $\endgroup$ – Doktor J Nov 2 '16 at 14:27
  • 4
    $\begingroup$ Not only is it correct, but I think every four-coloring of this map can be obtained from this one by some sequence of rotation, reflection, or swapping colors (for example, rotate $120$ degrees, then reflect through the vertical line through the center, then swap the red and blue colors, then swap the blue and green colors). $\endgroup$ – David K Nov 2 '16 at 14:58
  • 18
    $\begingroup$ +1 for having a relatively color blind friendly coloring. At least compared to other colorings on this page. $\endgroup$ – Asaf Karagila Nov 2 '16 at 23:15
  • 12
    $\begingroup$ I can imagine Google using that design for one of their products. $\endgroup$ – camden_kid Nov 3 '16 at 17:09
  • $\begingroup$ @DavidK: I noticed the same thing about all the answers here. Do you have an idea of a proof? $\endgroup$ – tomasz Nov 3 '16 at 21:40
42
$\begingroup$

A few people have commented that all of the answers given so far have been identical up to symmetry (either by exchanging colors, or by using a symmetry of the uncolored diagram). Here's a proof that the answer that everyone has given is the only possible answer, up to symmetry.

Let me number the regions, like so:

Numbered map

Without loss of generality, assume that region 1 is red, region 2 is green, and region 3 is blue.

Is region 10 yellow? I will prove that it is not. Suppose that region 10 is yellow. Then since region 5 borders regions 1 (red), 2 (green), and 10 (yellow), region 5 must be blue. Next, since region 6 borders regions 2 (green), 5 (blue), and 10 (yellow), region 6 must be red. Now region 7 borders regions 2 (green), 3 (blue), 6 (red), and 10 (yellow), so it cannot be colored. This proves that region 10 is not yellow.

We now know that region 10 must be red, green, or blue. Without loss of generality, assume that region 10 is red.

Now we can find:

  • Region 7 borders regions 2 (green), 3 (blue), and 10 (red). Therefore, region 7 is yellow.
  • Region 6 borders regions 2 (green), 7 (yellow), and 10 (red). Therefore, region 6 is blue.
  • Region 5 borders regions 1 (red), 2 (green), 6 (blue), and 10 (red). Therefore, region 5 is yellow.
  • Region 8 borders regions 3 (blue), 7 (yellow), and 10 (red). Therefore, region 8 is green.
  • Region 9 borders regions 1 (red), 3 (blue), 8 (green), and 10 (red). Therefore, region 9 is yellow.

At this point, the only uncolored region is region 4. Its neighbors are regions 1 (red), 5 (yellow), 9 (yellow), and 10 (red). We can complete the coloring by choosing either green or blue. Both choices will give the same coloring, up to symmetry.

$\endgroup$
  • $\begingroup$ Nice work. FWIW, using Knuth's AlgorithmX with the first 3 colours fixed as per your answer, I get these solutions: RGBGYRYRYB, RGBGYRYGYB, RGBGYBYGYR, RGBBYRYRYG, RGBBYBYRYG, RGBBYBYGYR; in numeric form that's 0121303032, 0121303132, 0121323130, 0122303031, 0122323031, 0122323130. $\endgroup$ – PM 2Ring Nov 3 '16 at 14:26
32
$\begingroup$

This works, as you can check..

enter image description here

$\endgroup$
29
$\begingroup$

Although I wouldn't call it an algorithm, you can construct a solution equivalent to those of the other three answers via this rational approach:

  1. Assign a color C1 to the outer ring. It's a promising candidate because of the symmetry and topology of the figure.

  2. Observe that

    • the outer ring has no boundary in common with the inner disk, so C1 can be re-used there
    • each region of the inner disk borders the other two, so these three regions must each have a distinct color
  3. Therefore choose two more colors C2 and C3, and assign C1, C2, and C3 as the colors of the regions of the inner disk. It doesn't matter which color is assigned to which region, as all arrangements are interconvertible by symmetry operations on the figure, as partially colored in step (1).

  4. Observe that there is exactly one segment of the middle ring that borders both C2 and C3 from the inner disk; it also, perforce, borders C1 from the outer ring. That segment requires a fourth color, C4.

  5. The color assignments made to this point leave only one choice each (without using a fifth color) for the remaining middle-ring segments other than the one opposite the region assigned in the previous step. Having made those assignments, two alternatives remain for the final region; either can be assigned.

$\endgroup$
21
$\begingroup$

One possible 4-coloring of such.

enter image description here

$\endgroup$
6
$\begingroup$

To answer the "algorithmically" question, this map has some regions that only border four others. There is a relatively short, algorithmic proof that if you can 4-colour all but one of the regions of a map, and the last region, R, only borders four others (call them R_1, R_2, R_3, R_4 in clockwise ordering about R), then you can colour the whole map. To do this, work as follows. It is easy unless R_1 to R_4 already use all the colours. Say they are blue, green, red, yellow in that order around region R. Now we try to recolour R_1 to red, in the hope that this will allow us to colour R blue. If we do that, we have to recolour any red region which borders R_1 blue. Then we have to recolour any blue region which borders one of these red, and so on. We keep doing this until we run out of things to recolour. Now one of two things happens: either we can colour R blue or we had to recolour R_3 blue. In the latter case, there was a chain of red and blue regions stretching from R_1 to R_3, but there can't also be a chain of green and yellow regions stretching from R_2 to R_4 (they have to cross somewhere, but the fact that they use different colours means that they can't). So now if we try the same trick recolouring R_2 yellow, any yellow regions next to R_2 green, and so on, this time we won't have to recolour R_4, and we will be able to colour R green.

We've now shown that if we can colour everything apart from a region that meets four (or fewer) others, we can do this recolouring trick and then colour the last region. Similarly, if we had a colouring of some of the regions, and one of the uncoloured regions only bordered four coloured ones, we can recolour in this way and then colour that region as well. So if we can find an ordering of regions such that each one borders at most four previous ones, we can progressively recolour in this way. In this map we can -- basically progressively remove regions that only have four neighbours in what's left, then reverse that ordering -- so this algorithm will work.

This method was the basis of Kempe's incorrect proof of the 4-colour theorem, and was used by Heawood to prove the 5-colour theorem (using five colours we are ok so long as there is always a region we can remove which borders at most five others, but that is true for any plane map). It can be used to easily find a 4-colouring of Martin Gardner's "April Fools" map, which would be very difficult to find by trial and error.

$\endgroup$

protected by Community Apr 1 '17 at 6:04

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.