logical deduction - 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?

Answer

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.