Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Does adjacency in this problem not include single-point adjacency?

share|improve this question
11  
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
1  
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? –  Christopher Pfohl Jan 2 '13 at 19:10
8  
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
4  
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
3  
Also not considered are multiple-component regions, eg Michigan. –  alancalvitti Jan 2 '13 at 19:12

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.