23
$\begingroup$

The Four color theorem states that no more than four colors are required for any map. Can it be proved or disproved that 3 colors can be used for United States map?

$\endgroup$
  • 1
    $\begingroup$ brute force, that's how the 4 color proof was construced :) $\endgroup$ – ratchet freak May 17 '14 at 23:19
  • $\begingroup$ I think this is a question of geometry. $\endgroup$ – Brian J. Fink May 18 '14 at 22:38
  • 3
    $\begingroup$ Note that 4 colors may not suffice if there are exclaves. I don't know whether this is a problem for the US. $\endgroup$ – Gilles May 19 '14 at 0:01
  • $\begingroup$ @Gilles: There are, but AFAIK none that affect the adjacency graph of the states. $\endgroup$ – dan04 Mar 24 '16 at 5:15
49
$\begingroup$

I started by assuming two adjacent states must be different colors. Therefore, I arbitrarily assigned blue to California and beige to Oregon.

  • Nevada must therefore be a third color: green.
  • Arizona must therefore be neither green nor blue: beige.
  • Utah must therefore neither be green nor beige: blue.

Idaho must therefore be neither beige, green, nor blue - which disproves the ability of the US map to be covered by three colors. Idaho, here highlighted in dark red, must be color number 4.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ +1. Short, sweet, and to the point. Also, you included Utah. ;) $\endgroup$ – Xynariz May 20 '14 at 20:56
  • 2
    $\begingroup$ I don't see any orange on that map (just a gray Oregon and Arizona); either you or I am colorblind. $\endgroup$ – IQAndreas May 27 '14 at 1:06
  • 6
    $\begingroup$ @IQAndreas - The "orange" looks very beige to me. $\endgroup$ – Bobson Jul 2 '14 at 21:01
  • 9
    $\begingroup$ If you look at these states as a graph, these states minus Nevada form a cycle of odd length... which itself requires three colors. Add Nevada, which is adjacent to each, and you require a fourth. $\endgroup$ – TheRubberDuck Sep 19 '14 at 18:24
10
$\begingroup$

That four colors will suffice may be easily shown by the fact that four-color maps exist. That three colors will not suffice may readily be shown by pointing out particular places where it is insufficient, but it may be more enlightening to point out a required condition for three-coloring: if a region is encircled by other regions, and at most two of them touch it at any point, then none of those regions may be the same color as the encircled reason, and they must have three different colors unless the number of such regions is either one (in which case one color would obviously suffice for it) or there are an even number (in which case two would suffice). Many land-locked states other than Colorado, Utah, Arizona, and New Mexico (the only states to meet more than two neighbors at a single point) have an odd number of neighbors; thus, any region of the map containing such a state and its neighbors would require four colors.

$\endgroup$
7
$\begingroup$

3 colors are not sufficient for a map of the US.

Take a look at this 4-color US map I found online.

enter image description here

Look at Oklahoma. It has a lot of edges and touches a lot of other states. If you only had 3 colors, there would be no way to color that section. Make Oklahoma color 1, and then start alternating colors for the surrounding states. Kansas is 2, Colorado is 3, New Mexico is 2, Texas is 3, Louisiana is 2, and here's where it breaks down: Arkansas is touching both Texas and Oklahoma. There's no way to color those so that they don't conflict with Oklahoma and Texas. See this edited version of the map:

enter image description here

Arkansas can't be yellow, green, or pink. So you must have a fourth color.

$\endgroup$
  • 10
    $\begingroup$ Your example is flawed since Louisiana isn't touching Oklahoma. Couldn't then Louisiana be yellow, allowing Arkansas to be pink, and Missouri green? $\endgroup$ – IQAndreas May 27 '14 at 1:04
  • 1
    $\begingroup$ It might also be clearer if you use use gray for all state colors that you aren't using in your example. Here is an SVG version of the map of USA on Wikipedia to make it easier: commons.wikimedia.org/wiki/File:Map_of_USA_four_colours.svg $\endgroup$ – IQAndreas May 27 '14 at 1:16
  • $\begingroup$ Strictly speaking this coloring is invalid, because Illinois and Michigan share a common border (it's underwater in Lake Michigan) and therefore cannot both be dark blue. But you can fix it by making Ohio dark blue and Michigan red. $\endgroup$ – Nate Eldredge Aug 19 '16 at 18:13
2
$\begingroup$

Another demonstration:

The graph of the US contains a 4-clique: four states which are mutually adjacent. That is, any two of these four states share a common border (of nonzero length), and therefore cannot receive the same color. (Obviously one-point borders do not count, so I am not talking about Arizona / Utah / Colorado / New Mexico.)

The states are:

New York, Connecticut, Massachusetts, and Rhode Island. The border between New York and Rhode Island is underwater, in Block Island Sound between Fishers Island and Napatree Point.

Note that

this is a special case of supercat's answer, because Connecticut is "encircled" by New York, Massachusetts, and Rhode Island. You cannot leave Connecticut without passing through one of those states (or its waters). Thus Connecticut is in some sense "landlocked" despite having a sea coast!

(I tried posing this as a new puzzle, in Four mutually adjacent US states (not the Four Corners), but it was closed as "trivia".)

$\endgroup$
  • $\begingroup$ I think it's worth noting that although NY and RI share a border, they do not share a visible edge and some mapmakers do assign them the same color. (In fact, even the four-coloring shown on Wikipedia does so.) $\endgroup$ – Will Aug 19 '16 at 21:03
0
$\begingroup$

Super cat is the closed to "proofification" in my opinion, maybe lacking in clarity (in my opinion). Though the other rather decent hand-wavy proofs.

As supercat points out it comes down to one region being landlocked and having an odd number of neighbors.

If we aim for a construction with 3 colors, we can choose colour A to be the central one.
And Color B to ANY adjacent one. Now as we only have 3 colours we are forced to choose a colour for the one clockwise of the B coloured one. This would be C. Which in turn has its clockwise neighbor forced.
This becomes proofy for odd numbers of neighbors as when we reach the spot counterclockwise of the original B colour, it has a minimum of 3 neighbors.

  • The first of the chain, B coloured.
  • the middle area, A coloured.
  • the second to last in the clockwise chain In the chain the pattern goes BCBCBC, where the 1st is B and the next is C

    Where every odd numbered one must be B, and even numbered C
    So the second to last in the chain is C as there are an odd number of neighbours
    and it is the second to last so it is an even one.

    So as the last in the chain is C, it has A, B, C neighbors. It cannot be A, B, or C: therefore it cannot be three coloured.

If all landlocked US states had an even number of neighbours you could 3 colour it. The reason I specify land locked is ocean adjacent states don't have a complete chain around them. Hope this answer adds some rigour and hopefully enlightenment to general 4 vs 3 Colouredness.

$\endgroup$
  • $\begingroup$ Your <pre> tag makes the formatting a mess. Using such a tag around the list might be excusable (though there are better ways to do the list in Markdown) but it's inappropriate for general paragraph-formatted text. $\endgroup$ – supercat Jul 12 '15 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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