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