Mathematics for Computer Science

Chapter 12 Planar Graphs494

s

t

u

r v

x

y

w

Problems for Section 12.8

Exam Problems

Problem 12.2.

b

c

d

e

a

g

h

i

f

j

k

l

m

n o

g 1 g 2 g 3

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

(d)Explain why all embeddings of two isomorphic planar graphs must have the
same number of faces.