Applying the 5-Color Proof to 4-Color Theorem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Suffusion of Yellow
Posts: 42
Joined: Thu Jan 01, 2009 6:15 pm UTC

Applying the 5-Color Proof to 4-Color Theorem

Postby Suffusion of Yellow » Fri Nov 13, 2009 12:18 am UTC

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 5-Color 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

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Applying the 5-Color Proof to 4-Color Theorem

Postby Tirian » Fri Nov 13, 2009 1:18 am UTC

You get a little hand-wavey 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.

Image

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Applying the 5-Color Proof to 4-Color Theorem

Postby skeptical scientist » Fri Nov 13, 2009 1:22 am UTC

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 pigeon-hole 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

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Applying the 5-Color Proof to 4-Color Theorem

Postby Tirian » Fri Nov 13, 2009 2:35 am UTC

Okay, I was on the right track.

Image

So here, the rub is that your blue-green Kempe chain and your blue-yellow 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 red-yellow Kempe chain in the interior of the cycle formed by the blue-green chain and the uncolored vertex, and similarly invert the red-green chain in the interior of the cycle formed by the blue-yellow 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.

User avatar
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 5-Color Proof to 4-Color Theorem

Postby jestingrabbit » Fri Nov 13, 2009 4:28 am UTC

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 pigeon-hole 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 de-identify your identified vertices, and then the neighbors of the vertex you deleted are 3-coloured, 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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests