Mathematics for Computer Science

Chapter 12 Planar Graphs380

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)

s

t

u

r v

x

y

w

Problems for Section 12.8

Exam Problems

Problem 12.2.

(a)Describe an isomorphism between graphsG 1 andG 2 , and another isomor-
phism betweenG 2 andG 3.

(b)Why does part.a/imply that there is an isomorphism between graphsG 1 and
G 3?

LetGandHbe planar graphs. An embeddingEGofGis isomorphic to an em-
beddingEHofHiff there is an isomorphism fromGtoHthat also maps each
face ofEGto a face ofEH.

(c)One of the embeddings pictured above is not isomorphic to either of the others.
Which one? Briefly explain why.