The question Is there a proof that a map of the United States requires 4 colors? was answered by showing that Nevada has five neighbors, each adjacent to the next (an "odd wheel"). "Adjacent" here means that they have a common border which is more than a single point.
Another possible proof would be to find a state with three neighbors, each adjacent to the next. That would constitute a "4-clique": four states which are mutually adjacent, in that each one is adjacent to each of the three others. (By our definition of "adjacent", Utah / Arizona / New Mexico / Colorado does not count.)
There actually is a 4-clique in the map of the United States. What are the four states?
Answer
New York, bordered by Rhode Island, Connecticut, and Massachusets. The New York - Rhode Island border just happens to be under water, between Misquamicut Beach and Fisher's Island.
No comments:
Post a Comment