1.2 Isomorphisms and Automorphisms17010OdZ人KAFig.1.10.where the sum is over all unlabelled simple graphs on n vertices. In particular, thenumber of unlabelled simple graphs on n vertices is at least[2(2]](1.2)元For small values of n,this bound is not particularly good.For example, therare four unlabelled simple graphs on three vertices, but the bound (1.2) is justtwo. Likewise, the number of unlabelled simple graphs on four vertices is eleven(Exercise 1.2.6), whereas the bound given by (1.2) is three. Nonetheless, when nis large, this bound turns out to be a good approximation to the actual numberof unlabelled simple graphs on n vertices because the vast majority of graphs areasymmetric (seeExercise1.2.15d)Exercises1.2.1a) Show that any isomorphism between two graphs maps each vertex to a vertexthe samedegreeb) Deduce that isomorphic graphs neceessarily have the same (nonincreasing) de-greesequence.1.2.2 Show that the graphs in Figure 1.1l are not isomorphic (even though theyhavethe same degree sequence)1.2.3 Let G be a connected graph. Show that every graph which is isomorphic toG is connected.1.2.4Determinea) the number of isomorphisms between the graphs G and H of Figure 1.71.2 Isomorphisms and Automorphisms 17 v1 v1 v1 v1 v1 v1 v1 v1 v2 v2 v2 v2 v2 v2 v2 v2 v3 v3 v3 v3 v3 v3 v3 v3 Fig. 1.10. The eight labelled graphs on three vertices where the sum is over all unlabelled simple graphs on n vertices. In particular, the number of unlabelled simple graphs on n vertices is at least 2( n 2) n! (1.2) For small values of n, this bound is not particularly good. For example, there are four unlabelled simple graphs on three vertices, but the bound (1.2) is just two. Likewise, the number of unlabelled simple graphs on four vertices is eleven (Exercise 1.2.6), whereas the bound given by (1.2) is three. Nonetheless, when n is large, this bound turns out to be a good approximation to the actual number of unlabelled simple graphs on n vertices because the vast majority of graphs are asymmetric (see Exercise 1.2.15d). Exercises 1.2.1 a) Show that any isomorphism between two graphs maps each vertex to a vertex of the same degree. b) Deduce that isomorphic graphs necessarily have the same (nonincreasing) de￾gree sequence. 1.2.2 Show that the graphs in Figure 1.11 are not isomorphic (even though they have the same degree sequence). 1.2.3 Let G be a connected graph. Show that every graph which is isomorphic to G is connected. 1.2.4 Determine: a) the number of isomorphisms between the graphs G and H of Figure 1.7