Subj:     Puzzle - Map Coloring (S502c) 
          From: The Handley Math Page on 9/5/2006
Source: http://www.pen.k12.va.us/Div/Winchester/jhhs/math/puzzles/map1.html

To create maps that are easy to read, mapmakers often color them according to a rule that touching regions must always be colored differently. To color a large, complicated map this way, you might think you'd need to use a lot of different colors. But in fact, it has been proven mathematically that you never need more than four colors, no matter what the map looks like.

Francis Guthrie made this conjecture in 1852, but it remained unproven until 1976, when Wolfgang Haken and Kenneth Appel showed that it was true!



Also, quite interestingly, this proof required the assistance of a computer to check 1,936 different cases that every other case can be reduced to! To date no one knows a quick short proof of this theorem. 

The drawings below aren't maps, but the same principle applies to them. Can you find a way to color all the regions in each drawing, using no more than four different colors, so that regions of the same color never touch (except at corners)? Here's a handy hint: Before coloring a pattern, plan how you will do it by penciling in the names of your chosen colors in each region.