Planar Graphs, K5 and K3,3

K5 and K3,3

A planar graph can be drawn in the plane, or on a sphere, wiith no edge crossings. Edges need not be straight lines, but they must be continuous paths.

K4 is planar, but how about K5 or higher? Pick three of the 5 points and draw the triangle. If the fourth point is outside, exchange inside for outside, so the fourth point is inside. Connect it to the other three. If the fifth point is outside it can't connect to the fourth. If it is inside it will be cut off from one of the first three points. Hence K5 is not planar, nor any graph that contains it. All this requires things like the Jordan curve theorem if you want to be rigorous, but the naive intuition is correct. (Limerick)

K2,3 is planar; how about K3,3? Take the six vertices in sequence, alternating between the two sets. This creates a hexagon, or something equivalent to a hexagon. We have three more lines to draw, the three diameters. Only one can be drawn inside; two would cross. Similarly, only one can be drawn outside. Thus K3,3 is not planar.