# If a graph can be colored with max 4 colors, is it planar?

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$):