Mathematics for Computer Science

12.8. Classifying Polyhedra 381

b

c

d

e

a

g

h

i

f

j

k

l

m

n o

g 1 g 2 g 3

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

Problem 12.3. (a)Give an example of a planar graph with two planar embeddings,
where the first embedding has a face whose length is not equal to the length of any
face in the secoind embedding.

(b)Define the length of a planar embedding,E, to be the sum of the lengths of
the faces ofE. Prove that all embeddings of the same planar graph have the same
length.

Problem 12.4. (a)A simple graph has 8 vertices and 24 edges. What is the average
degree per vertex?

(b)A connected planar simple graph has 5 more edges than it has vertices. How
many faces does it have?

(c)A connected simple graph has one more vertex than it has edges. Is it neces-
sarily planar?

(d)If your answer to the previous part wasyes, then how many faces can such a
graph have? If your answer wasno, then give an example of a nonplanar connected
simple graph whose vertices outnumber its edges by one.

(e)Consider the graph shown in Figure 12.17. How many distinct isomorphisms
exist between this graph and itself? (Include the identity isomorphism.)