I'm pretty sure I'm missing something obvious here and this is going to be embarrassing, but for the life of me I can't figure out what it is, soooo...why can't you apply basically the proof of 5 color theorem (this one http://www.proofwiki.org/wiki/Five_Color_Theorem) to the four color problem, with slight modification?
In particular, can't you say that
1) by Euler's formula the smallest possible graph that can't be colored by four colors has at least one region that neighbors exactly five other regions
2) by deleting this region, coloring the resulting graph with four colors, then reinserting it with a fifth color you get a graph which is four colored except for one pentagon, which is a fifth color
3) if the pentagon doesn't neighbor a country of each of the four colors, color it the missing color and you're done (trivial case.) If it does, then it must border exactly one of these colors twice (pigeonhole principle, it has five neighbors in four colors.)
4) There are two cases here.
A) The countries colored in the color that appears twice are right next to each other.
In this case, you basically do the 5Color proof on the other three countries: if there is no walk between the flanking two in those two colors, you can look at the subgraph which extends from one of them and contains only those two colors and invert it. If there is such a walk, then there is no such walk from the middle country to either of the two that are colored the same, so do the same trick with those.
B) The countries colored in the color that appears twice are one away from each other in one direction and two away from each other in the other.
In this case, if there is no walk between the single country in between and either one of the two that are together, you can invert one of them as above and you're done. If there is such a walk between both, there can't be one between each of the same colored two and one of the three remaining countries, so you invert both of them and color the pentagon the color which initially appeared twice.
Either way, you get a 4 coloring of the graph, contradicting the assumption that you could not four color the graph.
Does that make sense? What am I missing?
I know this is a long post but hopefully someone's bored
Thanks guys,
Phil Kopel
Applying the 5Color Proof to 4Color Theorem
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 42
 Joined: Thu Jan 01, 2009 6:15 pm UTC
Re: Applying the 5Color Proof to 4Color Theorem
You get a little handwavey at the end there, so I don't know if it's you or me. Describe how step 4b would alter this graph to allow the white vertex to be colored.
ETA: Oh, I see where you're going. You want to recolor both blue vertices so that the white vertex can be blue, but recoloring them different colors.
Doing a little research into it, I suppose this is probably Kempe's flawed proof. SS is evidently wrong about the flaw being in the assumption that there is a vertex of degree 5, because the part about using Kempe chains on a vertex of degree 4 withstood scrutiny. Heywood found some flaw in the degree 5 case that I can not immediate find online, but it must be subtle because it took a while for the flaw to be uncovered. I am given to believe that Appel & Haiken discussed the flaw in their paper, so that would be a good place to look.
ETA: Oh, I see where you're going. You want to recolor both blue vertices so that the white vertex can be blue, but recoloring them different colors.
Doing a little research into it, I suppose this is probably Kempe's flawed proof. SS is evidently wrong about the flaw being in the assumption that there is a vertex of degree 5, because the part about using Kempe chains on a vertex of degree 4 withstood scrutiny. Heywood found some flaw in the degree 5 case that I can not immediate find online, but it must be subtle because it took a while for the flaw to be uncovered. I am given to believe that Appel & Haiken discussed the flaw in their paper, so that would be a good place to look.
Last edited by Tirian on Fri Nov 13, 2009 1:57 am UTC, edited 1 time in total.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Applying the 5Color Proof to 4Color Theorem
Well, the first mistake I see is that we can't assume that some region borders exactly five other regions, only that some region borders at most five other regions. If it borders at most three, you're fine, but if it borders exactly four you need some argument which doesn't rely on the pigeonhole principle. I haven't looked at the rest of your argument in detail, so I don't know whether that is the only mistake.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: Applying the 5Color Proof to 4Color Theorem
Okay, I was on the right track.
So here, the rub is that your bluegreen Kempe chain and your blueyellow Kempe chain meet at the blue vertex at the bottom, which throws a wrench in all of those nice Jordan curve arguments you had prepared. Kempe's argument (which works on my naive graph above) is that you can invert the redyellow Kempe chain in the interior of the cycle formed by the bluegreen chain and the uncolored vertex, and similarly invert the redgreen chain in the interior of the cycle formed by the blueyellow chain and the uncolored vertex. But it doesn't work on the Fritsch graph here because it would switch both the yellow and green vertices in the center to red, which is right out.
So here, the rub is that your bluegreen Kempe chain and your blueyellow Kempe chain meet at the blue vertex at the bottom, which throws a wrench in all of those nice Jordan curve arguments you had prepared. Kempe's argument (which works on my naive graph above) is that you can invert the redyellow Kempe chain in the interior of the cycle formed by the bluegreen chain and the uncolored vertex, and similarly invert the redgreen chain in the interior of the cycle formed by the blueyellow chain and the uncolored vertex. But it doesn't work on the Fritsch graph here because it would switch both the yellow and green vertices in the center to red, which is right out.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Applying the 5Color Proof to 4Color Theorem
skeptical scientist wrote:Well, the first mistake I see is that we can't assume that some region borders exactly five other regions, only that some region borders at most five other regions. If it borders at most three, you're fine, but if it borders exactly four you need some argument which doesn't rely on the pigeonhole principle. I haven't looked at the rest of your argument in detail, so I don't know whether that is the only mistake.
You're right that Euler's doesn't imply it directly, but degree 4 vertices aren't a problem.
Pick one, "delete" it to a list to be coloured later, and identify a pair of unconnected neighbors of that vertex (which exist as only one pair of opposing vertices can be connected). After you have a colouring for the rest of the graph, you deidentify your identified vertices, and then the neighbors of the vertex you deleted are 3coloured, so you can just put it back in and colour it the unused colour.
Apologies for algorithm speak.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Who is online
Users browsing this forum: No registered users and 10 guests