In response to the recent article regarding maps that require 4 or more colors…What about Bolivia? It is bordered by Peru, Paraguay, Brazil, Argentina, and Chile. During the 1800s it also bordered the Pacific. I think we would need more than 4 colors to map this region.
You don’t need more than four in order to avoid having adjacent polygons having the same color. In a map like you describe, colors might be duplicated, but the same color polygons do not have to be adjacent.
You can see this even more emphatically in the U.S. Tennessee is bordered by 8 states, Arkansas, Mississippi, Alabama, Georgia, North Carolina, Virginia, Kentucky, and Missouri.
Yet here is a map using four colors.
To expand on Cecil’s explanation, there was an old proof, from about a hundred years ago, that turned to have an error in it. However, the error was slight enough that a modified version successfully proved that you never needed more than five colors. That’s where the problem rested for decades.
Then Haken and Appel showed that the number of ways the old proof could go wrong was finite. So they programmed a computer to list the (roughly a thousand, I think) ways. Then they looked at one of the simple cases, and proved that that could be done with four colors, too. Then they told the computer to look at the other cases and create new variations on that proof. If the computer failed for a certain case, they solved it by hand again, and then had the computer do variations on that, until, at last, all the possible exceptions were proven not to be exceptions.
Just for clarification, it should be noted (since Cecil doesn’t expound at length on the “rules” of the game) that two regions are not adjacent if they share only one point. Thus, even if at the famous “Four Corners” intersection in the United States they created a fifth state that shared that point, it wouldn’t cause the four color rule to be violated.
Considering the changes in political geography since this columns first appear in 1984 (Europe and Asia are VASTLY different), has the four-color map been applied to the way the world is TODAY?
It doesn’t necessarily apply to countries, provinces, etc., in the real world, because they sometimes fail one of the important conditions of the four-colour theorem: their territories are not necessarily one continuous shape, but can have parts disconnected from other parts of the territory. Two examples are Alaska as part of the United States and Kaliningrad as part of Russia.
Pretty good article on it at Wikipedia: Four color theorem - Wikipedia
JWK: You are the first person to explain to me the use of the computer in solving the theorem so that I understood it.
Incidentally, I first learned about the theorem from a program on PBS. It had Max Headroom in it (or a clone) and some math detectives with days for last names. Anyone know the name of it?
ETA: Nevermind. It’s called Square One.
The examples above probably clarify things, but just to be clear . . .
Bolivia has five neighbors. None of these five neighbors can be colored the same color as Bolivia. However, one neighbor of Bolivia (say Peru), can have the same color as another neighbor of Bolivia (say Argentina), because Peru and Argentina don’t neighbor each other.
Square One was a great show. The segment with the detectives was “Mathnet”, a parody of “Dragnet”.
Not to mention water, which counts as a “country” for coloring purposes.
“That’s…
Infinity.
You can count forever;
There’ll always be one more!
That’s Infinity.
Count from dusk to dawn;
You’ll never reach Infinity, you’ll just go on
And on
And on and on and on
And on and on and on and on…”
“It was 9:00 A.M. in Los Angeles, and the smog was so thick you could cut it with a cliché.”
Yes, and would theoretically allow Britain, Ireland, and France to all be colored the same.
So just because a map could be colored with four colors doesn’t mean it’s a good idea!
Powers &8^]
There’s a point in Florida where five counties do come together at a point. IIRC, it’s in the middle of Lake Okeechobee.
And you could treat the ocean as a “country” for purposes of four-coloring, but then you might be forced to color some landlocked countries blue, too.
Well, the UK and the Republic of Ireland do share a land border, but the point remains.
I think you might run into problems with planarity if you consider the ocean, since it borders everything.
It doesn’t border landlocked countries, such as Switzerland.
Fair enough. But take a look at the South America map I linked to earlier, where the ocean borders all but two countries.
Take that map, make Venezuela and Suriname gray, and paint the water blue like land-locked Bolivia. You still need just four colors.