If you have a map broken down into regions with each region shaded a particular color. What is the most number of colors absolutely needed to color the regions such that no two adjacent regions share the same color no matter the layout of the map?
(I know the answer is 4. But can you prove it?)
2006-10-06 08:00:45 · 4 answers · asked by Anonymous in Science & Mathematics ➔ Mathematics
it is not an easy proof,
actually , it was done via a computer program.
The four-color theorem states that any map in a plane can be colored using four-colors in such a way that regions sharing a common boundary (other than a single point) do not share the same color. This problem is sometimes also called Guthrie's problem after F. Guthrie, who first conjectured the theorem in 1853. The conjecture was then communicated to de Morgan and thence into the general community. In 1878, Cayley wrote the first paper on the conjecture.
The result was finally obtained by Appel and Haken (1977), who constructed a computer-assisted proof that four colors were sufficient. However, because part of the proof consisted of an exhaustive analysis of many discrete cases by a computer, some mathematicians do not accept it. However, no flaws have yet been found, so the proof appears valid. A potentially independent proof has recently been constructed by Robertson et al. (Robertson et al. 1996, Thomas 1998).
At a Dec. 2004 scientific meeting in France, G. Gonthier of the Microsoft Research in Cambridge, England (working with B. Werner of INRIA in France) announced verification the Robertson et al. proof by formulating the problem in the equational logic program Coq and confirming the validity of each of its steps (Devlin 2005, Knight 2005).
2006-10-06 08:26:27 · answer #1 · answered by Anonymous · 2⤊ 0⤋
The proof of this was done in two parts: the first was a construction of a collection of 'basic graphs' that any counterexample would have to have. Then it was shown how to reduce any graph with those basic graphs down to four colors. Both parts were done by computer, although a lot of theoretical work was needed to allow the computers to be programmed correctly. The original basic list consisted of about 10000 graphs. I believe the number has been reduced to about 2000, but I'm not sure. In any case, the proof is too long to fit in this margin. ;)
2006-10-06 08:16:16 · answer #2 · answered by mathematician 7 · 2⤊ 1⤋
i guess the added perfect question is, why no longer? Why might want to we anticipate that tightening an elementary to teach sure might want to be elementary? If proving the tighter sure got here about through modifying the tactic for proving the looser sure, then particular we would want to anticipate some correlation in the complications of the proofs, yet when yet another approach needs to be devised, then some thing is going.
2016-12-04 08:26:51 · answer #3 · answered by embrey 4 · 0⤊ 0⤋
It has been "proved" by computer, though the proof has not been accepted by all mathematicians. So you're not going to see someone prove it here :)
2006-10-06 08:05:38 · answer #4 · answered by James L 5 · 1⤊ 2⤋