You should never need to use more than two colors! Here is one possible way to color my example using only two colors:

Here are some things to think about:

• Why do we never need more than two colors?
• Can you describe an algorithm to solve the problem using only two colors?
• Try to create an example on which your algorithm doesn't work. Why can't you?
• How about creating an example which others find hard to solve using only two colors?
• What would happen if we extended the definition of adjacent to include regions which shared a common vertex?
• Would that effect the minimum number of colors needed?
• What would happen if the shape we started with was not a square?
• How about if the lines used to create the regions weren't straight?
• Why doesn't it matter how many lines there are?