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?


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

  • 1
    $\begingroup$ Just for my own understanding, when you say a dense bipartite graph is "far from planar", are you making a rigorous mathematical statement? That is, can we quantify how close something is to being planar? I don't know enough graph theory to be able to tell. Thanks! $\endgroup$ – Jason DeVito Oct 6 '10 at 0:17
  • 6
    $\begingroup$ 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. $\endgroup$ – Alon Amit Oct 6 '10 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.