Chapter 11 Simple Graphs436
1
2
4 3
5
6
7
8 9
10
(a)G 11
2
4 3
5
6
8
9 7
10
(b)G 21
2
4 3
5
6
8
9 7
10
(c)G 31
2
3
4
6 5
8
9
7
10
(d)G 4Figure 11.25 Which graphs are isomorphic?isomorphism such that one graph has the property, but the other does not. For
at least one of the properties you choose,provethat it is indeed preserved under
isomorphism (you only need prove one of them).
Problem 11.7. (a)For any vertex,v, in a graph, let N.v/be the set ofneighbors
ofv, namely, the vertices adjacent tov:
N.v/WWDfujhu—viis an edge of the graphg:Supposef is an isomorphism from graphGto graphH. Prove thatf.N.v//D
N.f.v//.
Your proof should follow by simple reasoning using the definitions of isomorphism
and neighbors—no pictures or handwaving.