4
$\begingroup$

There's a theorem that every planar graph can be colored with $4$ colors in such a way that no $2$ adjacent vertices have the same color. Is the opposite true as well?

1 Answers 1

18

No. Consider $K_{3,3}$, the graph with two sets of 3 vertices each such that every vertex in one set is connected to every vertex in the other. It's not planar but can be colored with just 2 colors. More generally, take any dense bipartite graph - it's still 2-colorable, but far from planar.

A picture of $K_{3,3}$ (along with $K_5$):

alt text

  • 6
    Sure. You can consider the "crossing number" of a graph, which is just the minimal number of crossings you must have if you do insist of drawing it in the plane. There is "genus", which is the smallest number of holes in a surface in which the graph can be drawn without intersections. There are various other invariants which take the value "0" for planar graphs and can thus be considered a quantification of how non-planar a graph is.2010-10-06