3 ms·

Amazing project! Does anyone know why a (2D?) map will need at most four colors while avoiding neighboring areas with the same color?

• jonsen 12y ago
  "The four color theorem was proven in 1976 by Kenneth Appel and Wolfgang Haken. It was the first major theorem to be proved using a computer.": http://en.wikipedia.org/wiki/Four_color_theorem http://en.wikipedia.org/wiki/Four_color_theorem
• j2kun 12y ago
  This is a monumental theorem called the four-color theorem, which specifically states that ever planar graph is 4-colorable. It actually took mathematicians many years and many pages (and computer programs!) to prove. There is a simpler proof that every planar graph needs at most 5 colors. [1] Also, 2D is not quite specific enough. It turns out that there are non-planar graphs that can be drawn on a different kind of 2D-surface (the surface of a torus) that need more than four colors. [2] It turns out that for tori, the max number of colors is seven. And you can keep going up, culminating in this cool thing called the Euler characteristic. [3] [1]: http://jeremykun.com/2011/07/14/graph-coloring-or-proof-by-crayon/ http://jeremykun.com/2011/07/14/graph-coloring-or-proof-by-c... [2]: http://en.wikipedia.org/wiki/Toroidal_graph http://en.wikipedia.org/wiki/Toroidal_graph [3]: http://en.wikipedia.org/wiki/Euler_characteristic#Examples http://en.wikipedia.org/wiki/Euler_characteristic#Examples