Mathematics for Computer Science

Chapter 12 Planar Graphs374

for any embedding of a planar bipartite graph. By Euler’s theorem,fD 2 vCe.

Substituting 2 vCeforf in (12.5), we have

4.2vCe/2e;

which simplies to (12.4). 

Corollary 12.5.4.K3;3is not planar.

Proof. K3;3is connected, bipartite and has 6 vertices and 9 edges. But since9 >

2 
 6  4 ,K3:3does not satisfy the inequality (12.2) that holds in all bipartite planar

graphs. 

12.6 Another Characterization for Planar Graphs

We did not pick K 5 andK3;3as examples because of their application to dog

houses or quadrapi shaking hands. We really picked them because they provide

another, famous, discrete characterizarion of planar graphs:

Theorem 12.6.1(Kuratowski).A graph is not planar if and only if it containsK 5

orK3;3as a minor.

Definition 12.6.2. Aminorof a graphGis a graph that can be obtained by re-

peatedly^4 deleting vertices, deleting edges, and mergingadjacentvertices ofG.

Mergingtwo adjacent vertices,n 1 andn 2 of a graph means deleting the two ver-

tices and then replacing them by a new “merged” vertex,m, adjacent to all the

vertices that were adjacent to either ofn 1 orn 2 , as illustrated in Figure 12.12.

For example, Figure 12.13 illustrates whyC 3 is a minor of the graph in Fig-

ure 12.13(a). In factC 3 is a minor of a connected graphGif and only ifGis not a

tree.

The known proofs of Kuratowski’s Theorem 12.6.1 are a little too long to include

in an introductory text, so we won’t prove it. There are two further facts about

planarity that we will need in our proof that planar graphs are 5-colorable.

Lemma 12.6.3.Any subgraph of a planar graph is planar.

Lemma 12.6.4. Merging two adjacent vertices of a planar graph leaves another

planar graph.

(^4) The three operations can each be performed any number of times in any order.