# Four Color Theorem

My wife is making a quilt. She has a whole bunch of colors and is making a very simple pattern. I enjoy watching the whole process because it's very mathematical, but it has made me question the four color theorem because I've come up with a counterexample that indicates that I either:

1. Do not understand the problem.
2. Am missing a solution for this example.

The "counterexample" is this:

++++
+wx+
+yz+
++++


Unless w andz or x and y are allowed to be the same color you need 5 colors to make this work.

-
That is correct: it does not include single-point adjacency. Otherwise the four-corners states would provide a familiar core for a potential counterexample. –  Brian M. Scott Jan 2 '13 at 19:08
Right, that's what made me curious... If you did decide that single-point adjacency (correct term?) was adjacent how many colors would you need then? –  Crisfole Jan 2 '13 at 19:10
If single-point adjacency were admitted for consideration, then no number of colors would suffice, and the problem wouldn't be very interesting. –  Austin Mohr Jan 2 '13 at 19:11
If you allow single-point adjacencies then you can create maps that require arbitrarily many colors by cutting up a circle with all the pieces meeting at the center (like a pie). –  Jonathan Christensen Jan 2 '13 at 19:12
Also not considered are multiple-component regions, eg Michigan. –  alancalvitti Jan 2 '13 at 19:12

That is correct: it does not include single-point adjacency. Otherwise the Four Corners states of Utah, Colorado, Arizona, and New Mexico would provide a familiar core for a potential counterexample, one that would be hard for any cartographer to overlook. It’s also required that each region be a contiguous territory. A full informal statement of the theorem, adapted from Wikipedia:

Given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Two regions are said to be adjacent if they share a common boundary that is not a corner, where a corner is a point shared by three or more regions.

-