GeekDad Puzzle of the Week – Four Color States

One of my favorite theorems to learn about in math was the Four Color Theorem. The theorem states that any contiguous separation of a plane (called a map) can be completely colored by at most four colors such that no area touches another area of the same color. When my son, Max, asked for a US map to color, I saw my opportunity to introduce him to this theorem!
After printing a map of the Contiguous United States (no AK, HI), I challenged him to color the map so that no two adjacent states were the same color. After a small mishap in the midwest, he easily completed a map coloring. After changing the colors of a few states, we even produced a “balanced” coloring of the map, so that there were 12 states covered by each of the four colors he used. We even had fun tracing “paths” from coast to coast, from most any state to another while avoiding a selected color. For example, we were able to make it from California (blue) to Georgia (green) without touching any states that were colored yellow.

This week’s GeekDad Puzzle of the Week is the same challenge: Use the map (below) or a similar map to produce a balanced four color map of the contiguous US. Each correct entry will have a shot at winning this week’s fabulous prize, a ThinkGeek Gift Certificate.

For an additional challenge (and an additional entry in the prize drawing) explain why it may or may not be possible to trace a path from any given state to any other while avoiding a given color (assuming neither the start nor the end state is that avoided color.) For purposes of this part of the puzzle, consider the “Four Corners” (UT,CO,NM,AZ) to all be touching one another.

As always, please send in your response the GeekDad Central. Good luck, and happy puzzling!