A graph that can be drawn in the plane so that edges do not touch except at nodes is said to be a planar graph. For example the complete graph on four vertices K(4) appears at first not to be planar, but by rearranging the vertices, we will see that it is.

The complete graph on 5 vertices is not planar. The complete bipartite graph K(3,3) is also not planar. The previous assertions about the non-planarity of K(5) and K(3,3) are proved using Euler's formula. There is a theorem due to Kuratowski that a graph is planar if it contains neither a homeomorph of K(5) nor one of K(3,3).

--back to combinatorics--