Mathematics for Computer Science

11.11. References 435

(i)TheORof two properties that are preserved under isomorphism.

(j)The negation of a property that is preserved under isomorphism.

Class Problems

Problem 11.4.
For each of the following pairs of graphs, either define an isomorphism between
them, or prove that there is none. (We writeabas shorthand forha—bi.)

(a)

G 1 withV 1 Df1;2;3;4;5;6g; E 1 Df12;23;34;14;15;35;45g

G 2 withV 2 Df1;2;3;4;5;6g; E 2 Df12;23;34;45;51;24;25g

(b)

G 3 withV 3 Df1;2;3;4;5;6g; E 3 Df12;23;34;14;45;56;26g

G 4 withV 4 Dfa;b;c;d;e;fg; E 4 Dfab;bc;cd;de;ae;ef;cfg

Problem 11.5.
List all the isomorphisms between the two graphs given in Figure 11.24. Explain
why there are no others.

1

2

6

3 4

5

a

b

f

c d

e

Figure 11.24 Graphs with several isomorphisms

Homework Problems

Problem 11.6.
Determine which among the four graphs pictured in Figure 11.25 are isomorphic.
For each pair of isomorphic graphs, describe an isomorphism between them. For
each pair of graphs that are not isomorphic, give a property that is preserved under