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--