Mathematics for Computer Science

Chapter 12 Planar Graphs492

12.8 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.8.1(Kuratowski).A graph is not planar if and only if it containsK 5

orK3;3as a minor.

Definition 12.8.2.Aminorof a graphGis a graph that can be obtained by repeat-

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

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

ure 12.16(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.8.1 are a little too long to include

in an introductory text, so we won’t give one.

Problems for Section 12.2

Practice Problems

Problem 12.1.

What are the discrete faces of the following two graphs?

Write each cycle as a sequence of letters without spaces, starting with the alpha-

betically earliest letter in the clockwise direction, for example “adbfa.” Separate

the sequences with spaces.

(a)

b

e

f

g

c

d

a

(b)

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