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