From Wikipedia, the free encyclopedia

Mathematics desk
< December 29	<< Nov | December | Jan >>	December 31 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

Contents 1 December 30 1.1 Four Color Theorem

[edit] December 30

[edit] Four Color Theorem

I realize this is almost certainly a mistake, but I think I can four-color any graph fairly quickly. Given a planar graph, and given a stack to put vertices in temporarily that will keep track of what they were connected to,

• Any degree-0 vertex can be removed and pushed onto the stack. When it is added back on in the coloring stage, it can take any of the four colors.
• Any degree-1 vertex can be removed and pushed onto the stack. When it is added back on in the coloring stage, it can take any of three colors.
• Any degree-2 vertex can be removed and pushed onto the stack. When it is added back on in the coloring stage, it (depending on its surroundings) can take any of either two or three colors.
• Any degree-3 vertex can be removed and pushed onto the stack. When it is added back on in the coloring stage, it (depending on its surroundings) either can take any of either two or three colors, or must take a particular color.
• Any degree-4 vertex can be removed and pushed onto the stack. When it is added back on in the coloring stage, it (depending on its surroundings) either can take any of either two or three colors, or must take a particular color, or can take no color. In the event that it is adjascent to one of each color, one of its adjascent vertices must be recolored before coloring can continue.
• Any degree-5 vertex can be removed and pushed onto the stack. When it is added back on in the coloring stage, it (depending on its surroundings) either can take any of either two or three colors, or must take a particular color, or can take no color. In the event that it is adjascent to one of each of three colors and two of the fourth, one of its adjascent vertices must be recolored before coloring can continue.
• According to the articles, there exists no planar graph in which all vertices have degrees greater than five, so this will pull apart any graph and stack up its vertices in a convenient order. (Edit: More specifically, it will reduce each graph to a smaller one, which must also be reducible, and each reduction will follow a path that can be easily retraced in the opposite direction.)

Given a stack in which all vertices, when added back on to the graph so far reconstructed, will be adjascent to zero, one, two, three, four, or five other vertices,

• Since the first vertex will be degree-0, it can be colored anything.
• Any vertex that when added has degree 0, 1, 2, or 3, or that has degree 4 or 5 but is adjascent to fewer than four distinct colors, can be given any of the remaining colors, either randomly or in some arbitrary order of preference.
• Given a vertex that when added has degree 4 and is adjacent to four distinct colors, the new vertex will be called N, its adjascent vertices will be called a1, a2, a3, and a4 in clockwise order from the top, and their colors will be called A, B, C, and D, respectively. In order for the coloring to continue, one of the a-vertices will have to be recolored. Given an a-vertex and a color other than its own, either it can be recolored without effecting any of the other a-vertices, or it can't. Starting with a1 and C: If a1 is recolored C, any vertices adjascent to a1 that are colored C will have to be recolored. They can be recolored A to make things easy. Any vertices adjascent to those that are colored A will have to be recolored C, and so on. This recoloring system will trace out a subgraph that either includes another of the a-vertices (specifically a3, in this case) or doesn't, and that has no effect on any other part of the current graph. If it doesn't include any other a-vertex, this recoloring is acceptable and can be adopted. a1 will take C, N will take A, and coloring can continue. If it doesn't, then a2 can be recolored D. Five color theorem has a pretty good description of this point. If the subgraph includes both a1 and a3, then a2 and a4 are entirely separated from each other. No connected graph that includes only vertices of colors B and D can reach both of them. So, either a1 is recolored C, or a2 is recolored D, and the necessary recoloring can be done very quickly.
• Given a vertex that when added has degree 5 and is adjascent to three vertices of three different colors and two of the fourth, the new vertex will be called N, its adjascent vertices will be called a1, a2, a3, a4, and a5 clockwise, with a starting point that allows one of the first four to have the same color as the fifth, and their colors will be named A, B, C, and D, with D being the doubled-up color. a1, a2, a3, and a4 can be treated as with the degree-4 example, with the exception that no vertex colored D should be recolored. If such a situation comes up, the pairing can be reversed, and some other vertex can be recolored D.

Can anyone give me an example of a map (finitely sized) for which this would fail to find a four-coloring? Black Carrot 21:03, 30 December 2006 (UTC)

A graph with a vertex of degree greater than 5. Not all vertices can have degree > 5, but that does not imply that no vertex does.  --Lambiam^Talk 21:20, 30 December 2006 (UTC)

I thought someone might say that. If you look carefully, the strategy is to remove the vertices entirely, one at a time, then put them back together. When a vertex is removed, so are the edges connecting to it, and a record is kept of them so they can be put back later. "Taking them off and putting them back on" could be rephrased as "Finding a good order to color them in, then coloring each one with thought only for those already colored", and perhaps that would make it clearer. The point of the first half it to find a coloring order where as much freedom as possible is available, the point of the second half is to take advantage of that freedom. I've added that to the description above. Black Carrot 22:04, 30 December 2006 (UTC)

That is what I assumed. So then apparently the idea is that you remove vertices of lower degree first. I think your proof is then essentially the same as Kempe's proof of 1879, if I remember correctly.  --Lambiam^Talk 22:46, 30 December 2006 (UTC)

How is that what you assumed? You said the exact opposite. Maybe you were "testing" me? Anyway, I looked for Kempe on Google, and it sounds like you're right, but nobody bothers to explain how it was disproven. Can you point me in the right direction? Black Carrot 23:14, 30 December 2006 (UTC)

Kempe's "proof" of 1879 was shown to have a flaw by P.J. Heawood in 1890, who exhibited a map that showed that Kempe's proof failed. The paper is:

P.J. Heawood. Map colour theorems. Quart. J. Math., 24:332–338, 1890.

I'll see if I can find this map somewhere; if not, at least you have a citation for the paper, so you can do some searching yourself. —Bkell (talk) 23:24, 30 December 2006 (UTC)

Another somewhat interesting-looking paper, which might be easier to find, is

Fred Holroyd and Robert Glendinning Miller. The example that Heawood should have given. Quarterly Journal of Mathematics, 43(1):67–71, 1992.

I apparently don't have online access to this article, but if you can't find it, bug me in a couple weeks and I'll see if my library has a paper copy. —Bkell (talk) 23:32, 30 December 2006 (UTC)

Interesting. I'll see what I can do with that. I found a site that may or may not be what I'm looking for: [1]. It gives what I think are supposed to be the original counterexamples, but they're a snap to color in using this method, so I guess they must not be. If anyone can find a picture that's definitely supposed to be an exception, that would be awesome. I really don't see how this could be wrong. Black Carrot 00:10, 31 December 2006 (UTC)

Since it may take awhile to track this down, can anyone give me a hint? Some sort of foggy recollection out of the mists of the past? Is it, for instance, a flaw in the first half (choosing the order), or the second (coloring)? Black Carrot 00:12, 31 December 2006 (UTC)

I think now that your idea is related to Kempe's, but your actual proposed proof has a simpler flaw. Some terminology. Call two vertices entangled if they have different colours and are connected by a Kempe chain: a path of vertices that uses only two colours. Fact: If one of the vertices of a given face, having colour A, is not entangled with any other vertex of that face having colour B, then the graph can be recoloured in such a way that one or more vertices of the face have their colours changed from A to B, while all others are unchanged. Now for the degree-4 case it cannot be the case that a1 and a3 are entangled and at the same time a2 and a4 are entangled. If a1 and a3 are not entangled, you say, recolour a1 to C, else recolour a2 to D. You then reduce the degree-5 case to the degree-4 case, but with the exception that no vertex colored D should be recolored. However, if a1 is entangled with a5 and a2 with a4, then your degree-4 approach does not allow recolouring a2 or a4, but also not a1, since it requires giving a1 the colour of a3, which is the same as the colour of a5, so then a5 also has to be recoloured, but it had colour D (in the colour naming of the degree-5 case) and must not be recoloured.

If you try to fix this by swapping the roles of a3 and a5 and trying again, there is an enticing argument that it is impossible for both attempts to fail. That was Kempe's proof. It looks very convincing until you see the counterexample.

When I wrote: "That is what I assumed", I meant the fact that when a vertex is removed, so are the edges connecting to it, and a record is kept of them so they can be put back later. What I did not understand is that your first list of bullet points is not a discussion of the various possibilities that be encountered (can be removed), but a sequential program, to be executed in order, in which the commands are phrased in a civil way (for they must be removed). I was not testing you. In such proofs by inductive construction a simpler way of organizing the argument goes by induction. A graph with 0 vertices can obviously be coloured. Assume we can colour all graphs with n vertices. Let G be a graph with n+1 vertices. At least one vertex has degree < 6. Remove it, giving graph G'. Colour G'. Now <insert the essential argument here>.  --Lambiam^Talk 05:44, 31 December 2006 (UTC)

Yeah, I noticed that flaw before I went to bed last night. I can't believe I missed it, I was criminally careless with my analysis of the 5-case. As stated, and even slightly reformatted, that algorithm will always fail in certain situations. However, it's fairly easy to fix that, if more than one recoloration (two, in fact) is performed. I'll sketch what I mean as soon as I can.

Ah. Sorry about that. I like the induction. I'll keep that in mind. Black Carrot 16:02, 31 December 2006 (UTC)

Diagram:

It's a bit smaller than I'd intended, but I think it's still readable. The circle is the new vertex, the five points around it are already-colored vertices, the black lines are adjascency, the red lines are entanglements, the letters are colors, the 1 and 2 are to differentiate for discussion, and the numbering and coloring go clockwise from the black-bordered green dot. First, any instance can be rotated or flipped to match the black parts of one of these two diagrams. The basic question is, in order around the new vertex, are the same-colored vertices together, or apart? Left for the one, right for the other. Now, it would be reasonable to check whether the A, B, and C-colored vertices are entangled before anything else. If any of the three pairings are unentangled, that's the solution, and one of the pair can be recolored to match the other. If not, there are chains of alternating color following the paths sketched out by the red lines. In the case of the left-hand diagram, the B-colored vertex can be recolored D without any entanglements cropping up. In the case of the right-hand diagram, in the worst case of the right-hand diagram with as many additional entanglements as possible, no single recoloring will be possible (I checked them all, of course), but a double-recoloring would work fine. Recolor D1 to C and D2 to B. No entanglements can possibly get in the way, and the new vertex can be colored D. How Kempe thought he could deal with higher-degree vertices, which the things I've been reading hint he did, I can't imagine, but luckily that isn't necessary. Black Carrot 16:59, 31 December 2006 (UTC)

Congratulations, you have rediscovered Kempe's proof. Without loss of generality you may assume that in the original graph all faces are triangles, so there is no need to consider the case of the left diagram. As to your "double recolouring": Assume you start by recolouring D1 to C. This will, in general, cause other vertices to flip colour from C to D. These newly D-coloured vertices may constitute the missing links that now create a Kempe chain from B to D2. If that happens, the second recolouring ceases to be available. On the face :) of it this looks impossible, and definiyely so when you look at the diagram, but note that chains can cross. Heawood's counterexample was a concrete example where your and Kempe's double recolouring fails because each of the two available recolourings creates a new entanglement thwarting the other.  --Lambiam^Talk 19:03, 31 December 2006 (UTC)

Thank you. I don't understand what you're saying, though. I thought of that of course, and I chose them fairly carefully to avoid it. Here's how I see it:

In hindsight, I should have made them bigger. Again. However, hopefully my point is still visible. As you may be able to see, I've started out with a diagram of the relevant connections. This diagram is, as far as I can tell, identical to the actual graph, with the exception that unimportant vertices have been left out. (Each path would really be a tree, and there would be filler scattered around that isn't changed in either move and doesn't help in entangling anything.) I could draw that, and I've considered it carefully, but it doesn't seem necessary. By the way, I like this [2] website's idea of the "k-cluster". Ctrl+F that phrase, it's about halfway down. The idea of permuting a set of colors that shares no elements with another set seems clearer than the idea of recoloring. What's important is this: in order for one path to cross another, both have to intersect at a vertex (crossing edges is illegal), and that vertex can of course only have one color. Each loop that encloses a D (and it is in fact a loop), consists only of colors not in the set of colors being permuted. No crossing is possible, even once the switch has occurred. Could you show me an example where that would happen? Black Carrot 20:29, 31 December 2006 (UTC)

Found it. If the two loops holding the Ds in cross, each D can reach the other's loop, and act as gatekeeper, breaking the loop open.

This is, of course, a special case. Black Carrot 20:35, 31 December 2006 (UTC)

This is a better diagram.

I can't find a way to make this actually happen in a real recoloring, though. Are you sure this state is even reachable? Either way, there can't be no way around it at all, so I'll see what else I can find. Black Carrot 16:55, 1 January 2006 (UTC)

I don't know whether the situation can be reached with this specific graph. I'd be surprised, though, if it can't be reached with any graph, which is what you need to establish for saving the proof. Assume for the sake of argument that constructing a reachable Heawood-style counterexample proves very difficult – perhaps impossible. We would then have the new Black Carrot Conjecture that no Heawood-style counterexample provides a reachable situation (which, by the way, by itself is not a mathematically interesting statement). How to prove it? There is no reason to assume that this is any easier to prove than the original Four Colour Theorem.

If you want to spend your time on graph colouring, here is a purely combinatorial colouring conjecture that, if proved, immediately establishes the Four Colour Theorem. A simple contraction of a graph is a new graph obtained by the identification of two adjacent vertices. A (general) contraction of a graph is then any graph that can be obtained from the original graph by a sequence of zero or more simple contractions. The knit of a graph is the maximum size of any clique in any of its contractions. The conjecture is now that any graph whose knit equals K is K-colourable. The Four Colour Theorem follows from it by the observation that contraction preserves planarity, plus the fact that a clique of size 5 is non-planar.  --Lambiam^Talk 12:44, 2 January 2006 (UTC)

Well, either way, I found an example of a graph it'll fail on. So I guess the proof really is wrong. It turns out the same one was discovered by Errera years ago. Small world. Incidentally, do you happen to know how they got to the original disproof? The only thing I can think of that would have taken 11 years is if people were coloring things in randomly, and were really really unlucky. Black Carrot 21:08, 2 January 2006 (UTC)

No idea how it was found, but the following scenario seems plausible enough to me: Just everyone believed the proof until Percy Heawood read it and muttered under his breath: Wait a sec, is that a proof? And once he saw that the proof is flawed (for which you don't need a counterexample), an attempt to fix it quickly led him to a counterexample.  --Lambiam^Talk 09:51, 4 January 2006 (UTC)