the four color theorem...
in [Math]
|
Prev: integral
Next: math category of probability Chapt 3, Telescope as the the finest Distance tool measure in astronomy; 400 million light years as 1 atom/m^3 #83; ATOM TOTALITY
From: master1729 on 16 May 2010 03:21 i wrote : > > First, I have to say that I'm not a mathematician. > > Maybe that's why I > > don't understand why the four color theorem has > been > > so difficult to > > prove. > > The theorem states that no more than four colors > are > > necessary to > > color > > the regions of any map to separate them. > > My understanding goes like this: > > First you try to draw a counterexample. Then you > > realize it's > > impossible. And then you realize why: All the > regions > > have to touch > > all > > other regions - three goes fine, the fourth has to > > surround at least > > one > > of them which in turn frees its color for reuse. > > This problem seems to translate nicely into graph > > theory where the > > colors are dots and their contacts are lines > between. > > Given this, it's > > possible to draw a graph with 1, 2, 3 and 4 dots > with > > lines connecting > > all-to-all without any line crossing each other. > If > > you try to add a > > 5. > > dot, its connecting lines will have to cross an > > existing line; so, > > it's > > not possible to draw a graph with five dots > without > > any line crossing > > another line. See image: > > > http://noemata.net/ontheball/graph-4-color-theorem.png > > > This seems trivial, so why has the theorem been > > difficult to prove? > > Restating the theorem as: It is impossible to draw > a > > two-dimensional > > map > > where five or more colors are necessary, it then > > seems intuitively > > true > > via graph theory. Now the problem might still > exist, > > in the word > > "necessary" - who knows? > > For me this is proof enough. On the other hand my > > ideas are often > > crank... But what's wrong? > > i have a proof using infinite descent. in fact i even have the most efficient algoritm.
From: Jake Wildstrom on 16 May 2010 10:03 In article <160357148.135118.1273835097905.JavaMail.root(a)gallium.mathforum.org>, riderofgiraffes <mathforum.org_am(a)solipsys.co.uk> wrote: >> One imagines that such a map exists in some >> complicated way, but cannot find it. So I guess >> my question remains - why aren't we able to prove >> somehow that a map that needs 5 colors is >> structurally identical to a map where 5 regions >> have contact with each other? > >To the best of my knowledge that's an interesting and >useful conjecture, and it has been pursued. However, >no proof using that approach has been produced. Here >is what you seem to be saying: > >Conjecture: Any planar graph that requires 5 colours >for a vertex colouring is (in some sense yet to be >determined or defined) "structurally equivalent" to >K_5 - the complete graph on 5 points. A point worth investigation here -- if by "structurally equivalent", you mean "has as a minor", which is definitely a form of substructure, then what you are saying is in fact an extensively researched problem, namely Hadwiger's conjecture. Hadwiger's conjecture states that if a graph requires k or more colors, then the graph has a K_k as a minor (a minor being the result of "gathering together" any number of adjacent points and then taking a subgraph). The good news: Hadwiger's conjecture has been proven in the case k=5. The bad news: the proof is dependent on the Four-Color theorem being true in the first place. -Jake
From: Chip Eastham on 16 May 2010 10:49 On May 16, 6:50 am, noemata <noem...(a)kunst.no> wrote: > Reading and trying to reformulate of my argument: > (1) A map that needs n colours contains a K_n as graph. > (2) All maps can be restated as planar graphs. > Then, a map that needs more than 4 colours is impossible because it > would contain a non-planar K5 as graph. > > What about the counterexamples given, for example the pentagon graph > needing 3 colours while only having 2 mutually joined vertices? I > understand this as: while all maps can be restated as planar graphs, > not all planar graphs can be restated as maps. When I try to draw the > pentagon graph as map it reduces to a K3 as graph, which supports (1). > There isn't a direct way to draw a map from a graph - the example with > a pentagon with a vertex in the middle that requires 4 colours makes > this clearer. But there might be a procedure for this purpose that > reduces a planar graph to a K_n. For example, the node-list of the > pentagon shows that a couple of nodes are redundant and so leaving us > with a K3: > 1: 2, 3 > 2: 1 (redundant, already in "2: 3, 1") > 1: 2 (redundant, already in "1: 2, 3") > 2: 3, 1 > 3: 1, 2 > > In this way, would a simplified proof of 4CT be possible? Since 4CT, > as I understand it, is proven for all planar graphs, though not all > planar graphs are maps, the proof is more complicated than necessary. > Maybe all planar graphs /are/ maps, though not restate-able in a > direct way. Maybe all graphs can be reduced to maps. My idea is that > all planar graphs are reducible to a map as a K_n graph and thus > requiring n colours. > > Grateful for comments, my main concern is the relation between maps > and graphs. > -Bjørn > > On May 14, 2:22 pm, riderofgiraffes <mathforum.org...(a)solipsys.co.uk> > wrote: > > > > Thanks for very useful comments, many of the comments > > > here are, it's a great help. If any comments I made > > > were inappropriate, please put it on my slow-wittedness. > > > Nothing was inappropriate, and some of these issues are > > obscure and difficult. > > > > For instance I still don't agree on this one: > > > >> "If a map requires 5 colours then it must have > > >> five mutually adjacent points." > > > >> If that argument were valid, then so would this: > > > >> "If a map requires four colours then it must have > > >> four mutually adjacent points." > > > > I don't think the problem can be reduced like this. > > > A complete graph of 5 points might be "qualitatively > > > different" from one of 4 points in some respect. > > > If it is qualitatively different then you need to > > include that in your statement. As it was, you seemed > > to be saying that requiring five colours must in and > > of itself imply that there are five mutually adjacent > > points. Maybe it does, maybe it doesn't, but it's not > > right to make that claim without then qualifying it. > > > As stated, your method of reasoning seems to apply > > equally well to the four colour requires K_4 case, > > and we know that to be false. That then implies that > > the reasoning is faulty. If there is something > > special that starts to make it work in the five > > colour case then you need to make that clear. > > > And as I said, you might be right. It might be the > > case that a planar graph requiring five colours does > > then imply the existence of a planar K_5. If you > > can prove that then you have a valid proof of the > > 4CT, the first one that doesn't require a computer. > > > > Now, probably it's better for me to study the > > > answers and theorem more rather than to think > > > aloud - thanks again for useful help. > > > Sometimes you need to mess around with things on > > your own first, before reading other people's > > proofs. Then you are in a better position to > > understand the subtlties and difficulties. > > > Besides, sometimes you might find a proof that no > > one else has found. Unlikely, but possible. > > > never stop experimenting. > > > > Bjørn > > > Rider. > > I don't understand why you say that in drawing the "pentagon graph as map it reduces to a K3 as graph." To illustrate the ring of 5 regions in "map" form as opposed to "graph" form, take a circle and from the center draw five distinct radial line segments. The five "slices of the pie" are the regions, and each has two adjacent regions. No three regions are mutually adjacent, so there is no K_3 (triangle) in the corresponding (planar) graph. Yet the map requires 3 colors. regards, chip
From: noemata on 16 May 2010 14:51 On May 16, 4:49 pm, Chip Eastham <hardm...(a)gmail.com> wrote: > On May 16, 6:50 am, noemata <noem...(a)kunst.no> wrote: > > > > > Reading and trying to reformulate of my argument: > > (1) A map that needs n colours contains a K_n as graph. > > (2) All maps can be restated as planar graphs. > > Then, a map that needs more than 4 colours is impossible because it > > would contain a non-planar K5 as graph. > > > What about the counterexamples given, for example the pentagon graph > > needing 3 colours while only having 2 mutually joined vertices? I > > understand this as: while all maps can be restated as planar graphs, > > not all planar graphs can be restated as maps. When I try to draw the > > pentagon graph as map it reduces to a K3 as graph, which supports (1). > > There isn't a direct way to draw a map from a graph - the example with > > a pentagon with a vertex in the middle that requires 4 colours makes > > this clearer. But there might be a procedure for this purpose that > > reduces a planar graph to a K_n. For example, the node-list of the > > pentagon shows that a couple of nodes are redundant and so leaving us > > with a K3: > > 1: 2, 3 > > 2: 1 (redundant, already in "2: 3, 1") > > 1: 2 (redundant, already in "1: 2, 3") > > 2: 3, 1 > > 3: 1, 2 > > > In this way, would a simplified proof of 4CT be possible? Since 4CT, > > as I understand it, is proven for all planar graphs, though not all > > planar graphs are maps, the proof is more complicated than necessary. > > Maybe all planar graphs /are/ maps, though not restate-able in a > > direct way. Maybe all graphs can be reduced to maps. My idea is that > > all planar graphs are reducible to a map as a K_n graph and thus > > requiring n colours. > > > Grateful for comments, my main concern is the relation between maps > > and graphs. > > -Bjørn > > > On May 14, 2:22 pm, riderofgiraffes <mathforum.org...(a)solipsys.co.uk> > > wrote: > > > > > Thanks for very useful comments, many of the comments > > > > here are, it's a great help. If any comments I made > > > > were inappropriate, please put it on my slow-wittedness. > > > > Nothing was inappropriate, and some of these issues are > > > obscure and difficult. > > > > > For instance I still don't agree on this one: > > > > >> "If a map requires 5 colours then it must have > > > >> five mutually adjacent points." > > > > >> If that argument were valid, then so would this: > > > > >> "If a map requires four colours then it must have > > > >> four mutually adjacent points." > > > > > I don't think the problem can be reduced like this. > > > > A complete graph of 5 points might be "qualitatively > > > > different" from one of 4 points in some respect. > > > > If it is qualitatively different then you need to > > > include that in your statement. As it was, you seemed > > > to be saying that requiring five colours must in and > > > of itself imply that there are five mutually adjacent > > > points. Maybe it does, maybe it doesn't, but it's not > > > right to make that claim without then qualifying it. > > > > As stated, your method of reasoning seems to apply > > > equally well to the four colour requires K_4 case, > > > and we know that to be false. That then implies that > > > the reasoning is faulty. If there is something > > > special that starts to make it work in the five > > > colour case then you need to make that clear. > > > > And as I said, you might be right. It might be the > > > case that a planar graph requiring five colours does > > > then imply the existence of a planar K_5. If you > > > can prove that then you have a valid proof of the > > > 4CT, the first one that doesn't require a computer. > > > > > Now, probably it's better for me to study the > > > > answers and theorem more rather than to think > > > > aloud - thanks again for useful help. > > > > Sometimes you need to mess around with things on > > > your own first, before reading other people's > > > proofs. Then you are in a better position to > > > understand the subtlties and difficulties. > > > > Besides, sometimes you might find a proof that no > > > one else has found. Unlikely, but possible. > > > > never stop experimenting. > > > > > Bjørn > > > > Rider. > > I don't understand why you say that in drawing the > "pentagon graph as map it reduces to a K3 as graph." > > To illustrate the ring of 5 regions in "map" form > as opposed to "graph" form, take a circle and from > the center draw five distinct radial line segments. > > The five "slices of the pie" are the regions, and > each has two adjacent regions. No three regions > are mutually adjacent, so there is no K_3 (triangle) > in the corresponding (planar) graph. Yet the map > requires 3 colors. > > regards, chip Yes it's convincing. I didn't realize it before, though it does seem trivial. Also, if you or anyone has a quick answer: is it so that every planar graph can be directly restated as a map? Jake Wildstrom in the previous post made me realize I was more or less trying to reformulate Hadwiger's conjecture. In mathematical terms what i meant with the expression "pentagon graph as map reduces to a K3 as graph" is that the pentagon graph is "edge-contracted to a 3- cycle, that is, a K3 minor.", as it says on http://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory)#Special_cases Sorry if I have wasted anyone's time, thanks and regards, Bjørn
From: riderofgiraffes on 17 May 2010 01:44
To emphasise to the original poster, this reply from David Rusin is excellent and deserves close study. RiderOfGiraffes write: > Your argument is that because you cannot have five > mutually joined points, five colours cannot be > necessary. That means that if I have a graph without > four mutually joined points, four colours won't be > necessary. David Rusin replied: > Well, maybe you should say "In the spirit we might > expect..." instead of "That means..." . > > It might be helpful to the OP to demonstrate a graph > that really requires 5 colors but contains no K_5. > Building on the examples of other posts we might begin > with a ring of 5 points (the vertices of a pentagon) > and add two more vertices, each connected to all 5 > of the original points as well as to each other. That > way the pentagon requires 3 colors and each of the > additional points requires an additional color. On > the other hand any set of 5 mutually adjacent points > would have to include at least 3 points of the pentagon, > and no such set of 3 mutually adjacent points exists. > > This particular graph is not a counterexample to the > 4CT because it is not planar, but the fact that it is > not planar is not especially obvious, and moreover > there is no obvious way to use the planarity of the > graph to rule out a similar but more complex example > that IS planar. > > dave |