Forgive me if this has been covered before, but I couldn’t find it in the archives.
Any high-school geometry student can demonstrate the truth of the four-color map theory thusly:
On a flat map, any region must have either an odd or even number of neighbors.
If a region has an even number of neighbors, only three colors are needed – one for the “central” region, and two more to be used alternately in the neighbors.
If there are an odd number of neighbors, then a fourth color is needed for the “last” neighbor.
However, I’ve been told that a “demonstration” isn’t the same as a “proof.” I don’t debate that – what I want to know is why is the demonstration above not considered a proof?
> On a flat map, any region must have either
> an odd or even number of neighbors.
O.K., the problem with your “proof” is that you start by saying that any one region must have either an even or a odd number of neighbors. True, but then you go on to assume that every region on the map has either only even or only odd numbers of neighbors. You’re restricting the cases you consider already. Some maps have both regions with an even number of neighbors and regions with an odd number of neighbors.
In his book “Time Travel and Other Mathematical Bewilderments,” (Chapter 10, “Six Sensational Discoveries”) Martin Gardner shows exactly how the four-color theory was disproved.
My paraphrase:
H. S. M. Coxeter a geometer at the University of Toronto had suspected that this conjecture was false.
He was vindicated in November 1974 when William McGregor, a graph theorist of Wappingers Falls, NY, constructed a region of 110 regions that cannot be colored with fewer than five colors.
McGregor’s technical report appeared in 1978 in the “Journal of Combinatorial Theory,” Series B.
How 'bout dat?
(And don’t try to contradict this unless you’ve read the book.)
Forgive me if I’m being dense, but I don’t follow you. Yes, every region on the map would have either an odd or even number of neighbors. No matter which region you choose to start coloring in, you will need either three colors (even number of neighbors) or four colors (odd number of neighbors). Each of its neighbors would have either an odd or even number of neighbors, and the same rule applies. Each of those neighbors would have… and so on.
I don’t see how a map in which some regions have an odd number of neighbors and other regions have an even number of neighbors forms an exception.
I have just realized that it is possible that a region with an even number of neighbors may require four colors, if you started coloring in an adjacent region with an odd number of neighbors. But if you start coloring in elsewhere, the problem disappears.
Alright, I will look for the book. But I clearly remember somebody using a computer program to prove that four colors were the maximum necessary. I think that came along in the early '80s, and was even the subject of a US stamp. so it must be true!
Being utterly unqualified to judge between two competing mathematicians, I now tip-toe swiftly away…
One of the profs who worked on this, Wolfgang Haken, was my calc professor in college. He never could explain calculus worth a darn, so I’m glad to know he apparently had talents elsewhere.
You’re right, Haken couldn’t explain calculus worth a damn. Of course it might have something to do with english being a second language to him. Aside from the four color map thing, the thing I remember most about him was that he wore the same ugly sweater every day, and he smelled really bad. In fact, the entire math department was so full of europeans with only a passing aquaintence with soap that we began calling the aroma permeating Altgeld Hall as the stench of math.
The difference between a proof and a demonstration:
There is nothing in your demonstration that relies on the surface being flat. You could still make your odd-even argument (which is true LOCALLY). However, it is pretty easy on the surface of a torus (donut shape) to draw a map that requires more than four colours.
Aside from shape of surface (the assumption is a plane), the problem with this “proof” or demonstration is that it only addresses a central region surrounded by border regions without considering that those border regions might have neighbors OTHER than the central region with colors of their own to worry about. In other words, this demonstration only addresses maps with a hub and spoke shape.
I don’t understand – one of my conditions was a flat surface.
jens –
Maybe this is my failing, but I see the principle applying to any region anywhere on the map. Perhaps my error is in viewing every region as a hub.
Now, it is not too difficult to draw a “hub-and-spoke” arrangement that works just fine, and then draw additional regions in the third and fourth tiers that would require five colors. But you can re-assign colors to the same map, and it works just fine.
Maybe that’s it? The fact that this approach doesn’t work for every region you choose to start with, invalidates it as a general proof?
I dunno. I never had a problem understanding his words – just understanding the overall way he taught calculus. Several of us from class, being the budding scientists we were, did an experiment one time. Half of us paid no attention in class (or didn’t go) and read the related info from the book. The rest of us paid attention in class and tried to understand it, then went to the book. In both cases (the groups switched halfway through our experiment), those who listened to him before reading the book actually had more trouble understanding the material than those who just read the book!
I don’t remember the sweater, though I vaguely recall the smell. What I remember about the way he dressed was that his pants were always about 3 inches too short.
Here’s a counter example to your proof. The central country is bordered by an even number of countries, but two of the bordering countries that would be colored the same by your method actually border each other. Weird shapes are allowed by the problem, as long as the countries are contiguous. (That is, something like Michigan would violate the problem.)
I’m not sure what the applications of proving flat maps need only four colors is, but the general map coloring problem has many applications. The problem is to color a random map, flat or otherwise, with the minimum number of colors. This problem is in a class called NP complete. Basically that means that the fastest known way to solve them is to try every possible combination to see which is best, and yet there is no proof that this is the fastest possible method to solve them. There are many NP complete problems that look very different, but (and this is the fascinating part) if a faster method could be found to solve any one of them, then all of them could be solved by that same method. Now, such a method probably doesn’t exist since brilliant people have been searching for it for some time, but who knows? Finding it would be a huge boon to humanity.
Other NP complete problems:
Travelling salesman: Salesman wants to visit a given set of cities and return home. What’s the shortest possible route?
Knapsack: a burglar can only fit so much stuff in his bag. What objects should he take?
Longest path: a project has certain identified tasks. Some are dependent on others, while some can be run in parallel. What’s the shortest time of completion for the project?
It doesn’t matter about starting with Michigan. My point with Michigan is that it violates the map coloring problem entirely, while strangely shaped states/countries are allowable. It would be easy to come up with a flat map that required more than four colors if you allowed states/countries to be non-contiguous. I was just using Michigan as an example.
Whoa whoa. I’m really surprised. States and countries can be non-contiguous, but maps can still be colored with four colors (I’m thinking of Indonesia, Malaysia, etc.) Or so I thought. What’s an example of regions in two-dimensional space that can’t be colored in four colors with nobody sharing a border with a same-color region? I’m not assuming that it would be easy to describe, it’s just that I can’t even imagine it.
My “proof” (conceding in advance that it might not really be a proof) for the four color problem is to start out with a giant donut with a three-slice pie in the middle. That is, three mutually touching regions surrounded by a single circular region - each with a separate color. Now, no conceivable manipulation can require a fifth color.
It seems like (and I could be wrong) that there are a limited number of “geometrically significant” transformations you can do. Obviously, modifying the size of any region doesn’t really matter. What matters is ways of dividing the regions - each region can be divided or joined at will, but one of the four colors should do the job.
If you want, you can cut the outer donut into many regions, but no chunk of the donut can touch more than one of the inner pie regions, if any other chunk of the donut touches three.
If any chunk of the donut touches two of the pie slices, no other chunk of the donut can touch more than two.
If you want to cut the outer donut with a slice parrallel to the outer edge of the donut, say creating two concentric donuts or donut sections, that’s fine too, but not all of your skinny baby donuts can touch the pie in the middle.
But I won’t be surprised if this doesn’t constitute proof, since the standards of proof with this kind of thang seem pretty astronomical.
Non-fatal error:
You actually can have a big chunk of the outer donut touching three pie slices, and have another donut chunk touching two pie slices. But the chunk touching two can still be the same color as the pie slice it isn’t touching.
Easy. Five countries on ten islands, each island is owned by two countries, each country is on four islands, such that every country touches all the other–so you need five colors.
Part of your fatal error in your proof is the same as Beruang’s, you didn’t use the flatness condition in your proof. Since you didn’t, your proof should also work for the torus, but it obviously doesn’t. It is easy to draw seven (contiguous) countries on a torus so that they all touch each other. And it was proven long ago that seven was enough, for a torus.
