Is there a proof that a map of the United States requires 4 colors?

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?

• brute force, that's how the 4 color proof was construced :) Commented May 17, 2014 at 23:19
• I think this is a question of geometry. Commented May 18, 2014 at 22:38
• Note that 4 colors may not suffice if there are exclaves. I don't know whether this is a problem for the US. Commented May 19, 2014 at 0:01
• @Gilles: There are, but AFAIK none that affect the adjacency graph of the states. Commented Mar 24, 2016 at 5:15

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.

• +1. Short, sweet, and to the point. Also, you included Utah. ;) Commented May 20, 2014 at 20:56
• I don't see any orange on that map (just a gray Oregon and Arizona); either you or I am colorblind. Commented May 27, 2014 at 1:06
• @IQAndreas - The "orange" looks very beige to me. Commented Jul 2, 2014 at 21:01
• 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. Commented Sep 19, 2014 at 18:24

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.

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

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

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:

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

• Your example is flawed since Louisiana isn't touching Oklahoma. Couldn't then Louisiana be yellow, allowing Arkansas to be pink, and Missouri green? Commented May 27, 2014 at 1:04
• 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 Commented May 27, 2014 at 1:16
• 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. Commented Aug 19, 2016 at 18:13

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

• 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.)
– Will
Commented Aug 19, 2016 at 21:03

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.

• 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. Commented Jul 12, 2015 at 19:22