This is a monumental theorem called the four-color theorem, which specifically states that ever planar graph is 4-colorable. It actually took mathematicians man

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