Show that the following graph is not planar by finding a sub

Show that the following graph is not planar by finding a subgraph homeomorphic to K_3, 3.

Solution

Let us assume that K3 , 3 is planar and let G be a plane embedding of K3 , 3.

As K3 , 3 has no triangles and also, no odd cycles at all, every region of G must contain at least four edges.

Thus, 4r 2q = 18.

But we have, r 4.

Hence, by Euler’s formula,

2 = p q + r 6 9 + 4 = 1 ,which is a contradiction.

So, the graph K3 , 3 is nonplanar.