How to colour the US map with Yellow, Green, Red and Blue to minimize the number of states with the color of Green

Solution 1:

The minimum is two states that use the fourth color. Nevada and its five neighbors cannot be colored with only three colors, and similarly West Virginia and its five neighbors cannot be colored with only three colors. In both cases, once you color the center state one color (say, red), you can't use it again on its neighbors: without using green, they'd have to alternate yellow-blue-yellow-blue, but because the number of neighbors is odd, you'd get stuck at the end.

(In the comments, David K points out that Kentucky is a third state with the same problem: it has seven neighbors. But this doesn't force us to use a third green state, because Kentucky and West Virginia share a border and some common neighbors.)

Using only two green states is possible. If we color Arizona (dealing with the Nevada situation) and Ohio (dealing with West Virginia and Kentucky) both green, then the remainder of the map can be completed using only blue, red, and yellow:

Adjacencies between the states may be easier to see here.