Author |
Topic: Proving the 4-color theorem (Read 4145 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Proving the 4-color theorem
« on: Jun 17th, 2006, 5:31pm » |
 Quote  Modify
|
"Proof" of the 4-color theorem.
Can you find a flaw?
|
|
 IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Proving the 4-color theorem
« Reply #1 on: Jun 18th, 2006, 1:38pm » |
Quote Modify
|
Yes.
Besides the fact that point 12) is ridiculous.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Proving the 4-color theorem
« Reply #2 on: Jun 18th, 2006, 3:13pm » |
Quote Modify
|
What's ridiculous about 12? The split in the yellow regions is because there must be other regions (whose exact nature is immaterial to the proof, so they are not shown) which separate the two. These other regions share a common vertex with V, but not a border.
Regardless, 12 is also unneeded because, as I have shown above, you can prove the entire 4-color theorem from the special case of bridgeless tri-valent graphs. And for them, ryygb is impossible.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Proving the 4-color theorem
« Reply #3 on: Jun 19th, 2006, 10:02am » |
Quote Modify
|
I said that because usually only maps are considered where no more than 3 regions meet at a point. A map with a 4-fold frontier point can easily be converted into a map with 2 3-fold points and one extra frontier line, which is more difficult to color. So, proving the coloring is possible for maps without more-than-3-fold junctions proves it for all maps.
But it is true that according to the pictures, even maps with empty spaces between regions seem to be considered. So I understand why point 12 is there.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Proving the 4-color theorem
« Reply #4 on: Jun 19th, 2006, 10:48am » |
Quote Modify
|
on Jun 17th, 2006, 5:31pm, Icarus wrote:
I believe so, although I've read enough Martin Gardner that I could well just be remembering the flaw and not actually finding it...
Step 15 claims to use the argument of CASE 1 to show that a path exists, but case 1 actually says "either the sub-maps are disjoint, or a path exists." If the operation of step 14 changes the submap in step 15 to be disjoint, it may then only be possible to change one of the yellow regions to another color and not both of them.
For instance, in the given figure 2b, imagine that the green-blue path intersects the red-green path. Step 14 lets us exchange yellow and blue "within" the red-green path, but this operation could break the green-blue path, leaving two disjoint sub-maps. Now all we can do (by the logic of CASE 1) is exchange green and blue in one of the disjoint sub-maps, but this still leaves us with four unique colors (rbgyg replaces rygyb) bordering region v.
I lack the expertise to construct a map where this could happen (although I hinted at one possible direction above), or to prove that every possible 4-coloring of that map would lead to a failure. However, since the 4-color theorem was only proved (some would say "proved" in quotes) by computer in...the '70s?...I suspect such a counterexample must exist. 
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Proving the 4-color theorem
« Reply #5 on: Jun 19th, 2006, 9:02pm » |
Quote Modify
|
on Jun 19th, 2006, 10:02am, Grimbal wrote:| But it is true that according to the pictures, even maps with empty spaces between regions seem to be considered. |
|
No. The empty regions just represent parts of the map which do not come directly into the proof. The author is making no claims on the structure of these portions.
on Jun 19th, 2006, 10:48am, SMQ wrote:
That is pretty much how I see it. Note that the proof includes step 14 even though when you examine it's effect, all it does is exchange blue for yellow as the doubled color. You are still in the same situation after 14 as you were in before. Why include it? Because if you were to try to apply 15 immediately, using red-yellow paths to separate the blue-green sides so you could flip one side green for blue, it is obvious that there is no particular reason for it to be the red-yellow that connects and the blue-green that does not. However, if the blue-green connects and the red-yellow is broken into separate components, it does no good to flip red for yellow on one side, both red and yellow will still be present.
Note by the way that the mechanics described in CASE I are enough to prove the 5-color theorem.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Proving the 4-color theorem
« Reply #6 on: Jun 20th, 2006, 9:55am » |
Quote Modify
|
Hmm, maybe I can manage a counter-example afterall. 
Consider the map in A below, with colors corresponding to those of the given "proof." After step (14) we have B. But now step (15) fails because the green-blue chain has been broken, leaving two disconnected regions in the green-blue submap. While it is still possible to perform additional swaps to 4-color the map (C, D), the reasoning of the proof is shown to be incomplete.
It is also not necessary to show that every possible four-coloring of the map M-v would lead to failure, only that one does, as the proof does not specify any particular four-coloring of M-v. Indeed, if every possible four-coloring of M-v led to a failure, the FCT would be disproven, as the full map M would not then be four-colorable.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Proving the 4-color theorem
« Reply #7 on: Jun 20th, 2006, 4:21pm » |
Quote Modify
|
Well done!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Cahit
Newbie
Posts: 10
|
|
Re: Proving the 4-color theorem
« Reply #8 on: Jun 22nd, 2006, 8:36am » |
Quote Modify
|
Nice to see that there is ongoing discussion on the proof of the four color theorem. This time the proof technique is what I call "Kempe style inductive proof" which is very well known and is not correct. Some time ago, in order to overcome to the fallacious of the historical proof of Kempe one must use a joker color and double spiral-chain coloring (unfortunately my paper has been first accepted by arxiv prepint server and then removed because of its title). Anyway that is summarized in my web-article "THE FOUR COLOR THEOREM AND THREE PROOFS" ( http://www.emu.edu.tr/%7Ecahit/THE%20FOUR%20COLOR%20THEOREM%20---%20THRE E%20PROOFS.htm). The figures listed in the message reminds me again the need of using joker color and spiral chain coloring. Here is a map which explains my idea :
http://www.flickr.com/photos/49058045@N00/91749764/
Similar idea has been also given very recently by a Chinese mathematician Wan-Dong Xu "Pseudo Kempe-chain and a charted proof of the four-color conjecture" (download from http://www.paper.edu.cn/english/process/searchbyfieldnew_ok.jsp?page=2# )
Best
Cahit
P.S. Just note in map D (red-yellow) spiral chain and (blue-green) spiral chain that makes the double-spiral chain of the map.
|
| « Last Edit: Jun 22nd, 2006, 9:49am by Cahit » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print