4 ms·
> Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, ... > Do four colors su
by glitcher 7y ago
> Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, ...
> Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering).
I know very little about graphs and found this bit surprising. After some searching I found out it is called the Four Color Theorem.
Does anyone know of a resource that provides a more intuitive explanation for this for non-graph-theorists?
- urmish 7y agoIntuitive explanation about the proof? That might be tricky because it took a computer to prove it.
- intuitionist 7y agoYou can get some way there with a proof of the five-color theorem, though, which is much simpler. There’s also a good popular overview of the history of the problem in the book “Four Colors Suffice” by Robin Wilson.
- hawkice 7y agoIt required a notoriously hard-to-simplify proof, which required computer assisted brute force analysis. But an intuition is that a complete graph with four nodes is planar, and five is not. A (3,3) bipartite graph is also the smallest non-planar bipartite graph. That's probably good for answering "why would you suspect 4".
- jessriedel 7y agoTo save laymen a google: A complete graph is one where all the nodes are connected. A planar graph is one that can be draw in the plane without two lines intersecting.
- rocqua 7y agoNotably one you can draw on either a flat piece of paper or a sphere. On a torus, you need up to 7 colors.
- FreeFull 7y agoYeah, any graph of a sphere can be easily deformed to fit on a plane, with something like stereographic projection
- pmiller2 7y agoYep, and the proof that any graph that can be drawn without crossings on the torus can be properly colored with no more than 7 colors is vastly easier than the case for graphs drawn on the sphere/plane.
- achandlerwhite 7y agoNumberphile covered it well: https://www.youtube.com/watch?v=NgbK43jB4rQ https://www.youtube.com/watch?v=NgbK43jB4rQ It's also got a lot of videos on other cool math stuff.
- jnordwick 7y agoLOL. Not likely. The history of the proof is interesting. It was the first major proof that was done by computer. It reduced the set of graphs to about 2,000 and then brute forced it. Some refused to accept this was a "proof" in the traditional sense.
- avip 7y ago>I’m not an expert on the four color problem, but I assume the proof is true. However, it’s not beautiful. I’d prefer to see a proof that gives insight into why four colors are sufficient. P. Erdos
- pfdietz 7y agoThe proof has been formalized and verified in the Coq theorem proving system, which is good evidence it is correct.
- Twisol 7y agoThat wasn't really Erdős' issue with the proof. Unsolved problems in mathematics are often not important merely because of other problems that depend on them; you can look at the Riemann hypothesis to see how much work has already been done just assuming its truth. We're interested in these problems because we hope that the proof will teach new tools and grant new insights, and possibly spark other problems and generalizations. A proof that requires a computer to understand it is not helpful for these goals. The proof's veracity is not in question.
- pfdietz 7y agoI was responding to the "I assume the proof is true". There's really no reason to just assume that. Of course he's right that the proof was lacking in insight for human mathematicians. That's particularly important in combinatorics, which more than other areas of math grows by the accumulation of techniques rather than accumulation of results.
- anyfoo 7y agoAnd yet you assume that the problem was correctly stated in Coq, that the authors were using the software correctly, that they ran it more than once to account for random bit flips, that the authors are not just simply lying... while all those assumptions are reasonable, Erdös’s statement was as well.
- kccqzy 7y agoThe four color theorem is notoriously difficult to prove. However for intuitive understanding, you can look at the proof that five colors suffice to color any map. That proof should be understandable by anyone with an undergraduate level understanding of graph theory.
- emptybits 7y agoIn addition to the excellent Numberphile video suggested, I enjoyed this book quite a bit although it took me a while to get through. (I'm interested in graph theory but it's not my background or strength.) Includes plenty of math and illustrations and the human side of this solution's history. "Four Colors Suffice" by Robin Wilson