Treebeard's Homepage : Stumpers

# Treebeard's Stumper Answer15 December 2000

Four-Color Christmas

My design for a fancy Christmas tree is below, but it looks too plain for a greeting card without some bright holiday colors. The holiday stumper is to color in the tree using only four colors, with the special restriction that any adjacent regions with a common boundary must have different colors. The tree itself is part of the puzzle! A handy way to play with this stumper is to download the image and use a graphics program with a Fill tool to color in the regions. It also works to pencil in different letters. You will need to erase. Have a puzzling holiday!

My solution to the holiday stumper is below. The tree is colored with just four colors so that no adjacent regions are the same color. I started in the middle and worked outward. Then I worked in from the outside, adjusting colors when I had too. There are other solutions. (How many?) The four-color theorem is the claim that four colors are enough to color any design on a flat surface. This deceptively simple conjecture was finally proved in 1976 with an exhaustive computer analysis. This proves that a solution is possible, but that doesn't mean it's easy!

Notes:

Here's two more solutions from Graybear (left) and Alan Manning:

Graybear sent these comments:

I admit, I had to erase a couple of times while solving the stumper. In the central area I was using a repeating pattern of all four colors, but then realized that I should use a repeating pattern of three colors and reserve the fourth to resolve conflicts (the fourth color is the one I also used for the background). Once I got through that, I set about proving I couldn't do the star without having the two areas of the same color that meet at a point.

Assuming you color the background as I did, the three areas of the tree outside of the central area must be the other three colors. The trunk of the tree is the same color as the top. By looking at these areas first you can quickly determine if another solution is different than yours, regardless of the color scheme used.

 Alan Manning left the background white (a fifth color), so he was able to color the points of the star without colors meeting. It's officially ok for regions to touch at a point, otherwise the four-color theorem wouldn't have a chance. Think of a pie sliced into more than four wedges.

My design is a very slightly modified version of a design that Martin Gardner published in his classic Scientific American Mathematical Games column in the April 1975 issue as an April Fool's joke. This column is reprinted in Martin Gardner's collection Time Travel and Other Mathematical Bewilderments (W.H. Freeman and Company, 1988).

I added the star, the trunk, and one more L-shaped section in the lower right corner to fill a void. I also distorted the outside regions to make the tree, but it's obvious that stretching the shapes doesn't effect the problem as long as the boundries are preserved. That's a sign that this problem is a part of graph theory, a branch of topology. Connections matter, not exact shapes. I thought about writing a program to find solutions, but the hard part would be constructing a map that shows all the boundries in a logical rather than graphic way. I gave up. (A program that could make a connection map or graph from a computer graphic would be very useful. That's a non-trivial problem!)

Martin Gardner introduced his hoax like this:

As a public service, I shall comment briefly on six major discoveries of 1974 that for one reason or another were inadequately reported to both the scientific community and the public at large. The most sensational of last year's discoveries in pure mathematics was surely the finding of a counterexample to the notorious fou-color-map conjecture. That theorem, as all readers of this department must know, is that four colors are both necessary and sufficient for coloring all planar maps so that no two regions with a common boundary are the same color. It is easy to construct maps that require only four colors, and topologists long ago proved that five colors are enough to color any map. Closing the gap, however, had eluded the greatest minds in mathematics. Most mathematicians have believed that the four-color theorem is true and that eventually it would be established. A few suggested it might be Godel-undecidable. ] H.S.M. Coxeter, a geometer at the University of Toronto, stood almost alone in believing that the conjecture is false.

Coxeter's insight has now been vindicated. In November 1974 William McGregor, a graph theorist of Wappingers Falls, N.Y., constructed a map of 110 regions that cannot be colored with fewer than five colors. McGregor's technical report will appear in 1978 in the Journal of Combinatorial Theory, Series B.

William McGregor in fact did produce the map, and gave Martin Gardner permission to use it as part of his hoax. In a follow-up, Martin Gardner says what happened:
I never dreamed anyone would take it seriously, yet it produced more than a thousand letters from readers who did not recognize the column as a hoax.

The map was designed by correspondent William McGregor (his real name), who gave me permission to print it. Hundreds of readers sent me copies of the map, colored with four colors. Some said they had worked on it for days before they found a way to do it...

When Norman K. Roth published an article, "Map Coloring," in Mathematics Teacher (December 1975), many readers informed him that Scientific American had published a map disproving the four-color theorem. A letter from Roth in the following May issue pointed out that my column was "an apparently successful April Fools' article."

In 1977 the Vancouver Sun reported a British mathematician's claim (it turned out to be invalid) that he had proved the four-color map theorem. On January 17, 1977, the newspaper ran a letter from a lady in Port Moody, which said in part:

To set the record straight, I would like to bring to your notice the fact that the theorem has already been disproved by William McGregor, a graph theorist . . . in November 1975. He con- structed a map of 110 regions that cannot be colored with less than five colors. . . .
The four-color theorem was "proved" (or verified?) in 1976 by Kenneth Appel and Wolfgang Haken of the University of Illinois. Their controversal proof challenges the basic assumptions of what mathematical proof is. They used 1200+ hours of super-computer time to analyze 1,478 different configurations that in turn can produce every possible map on a plane. Martin Garner comments, "Whether a simple, elegant proof not requiring a computer will ever be found, is still an open question." It's interesting that such a simple, intuitive puzzle can be so difficult to settle! Co-author Kenneth Appel understands:
For almost a century and a half, a Holy Grail of graph theory has been a simple incisive proof of the Four Color Theorem. It has troubled our profession that a problem that can be understood by a school child has yet to be solved in a way that better illuminates the reason that only four colors are needed for planar maps. The feelings of many mathematicians were summed up for me by Herb Wilf's response to being told that it appeared that one could prove the theorem by a long reducibility argument which used computers to test the reducibility of a large number of configurations. He simply said, "God would not allow such a beautiful theorem to have such an ugly proof."

Here are some links for further research on the four-color theorem:

Back to Stumper