1 Graphs16rotational symmetry), as are the five vertices of the inner pentagon. The thirddrawing exhibits sixmilar vertices (under refective or rotational symmetry).namely the vertices of the outer hexagon. Combining these two observations, weconclude that all ten vertices of the Petersen graph are similar, and thus that thegraph is vertex-transitive.Fig. 1.9. Three drawings of the Petersen graphWe denote the set of all automorphisms of a graph G by Aut(G), and theirnumber by aut(G). It can be verified that Aut(G) is a group under the operationof composition (Exercise 1.2.9). This group is called the automorphism group ofG. The automorphism group of Kn is the symmetric group Sn, consisting of allpermutations of its vertex set. In general, for any simple graph G on n verticesAut(G) is a subgroup of Sn.For instance, the automorphism group of C, is Dn.the dihedral group on n elements (Exercise 1.2.10).LABELLED GRAPHSAs we have seen, the edge set E of a simple graph G =- (V,E) is usually consideredto be a subset of (2), the set of all 2-subsets of V; edge labels may then be omittedin drawings of suchgraphs.A simplegraph whose verticesare labelled.but whosdaenot, edalabeedsep,hera2f (), so 2(G) labelled simple graphs with vertex set V. We dendistinct subsbyGnthesetof labelled simplegraphs withvertex set (2.n)Theset G3 is shown in Figure 1.10.A priori, there are n! ways of assigning the labels ui+2,..., Un to the verticesof an unlabelled simple graph on n vertices. But two of these will yield the samelabelledgraphif thereisanautomorphism of thegraphmapping onelabellingtothe other. For example, all six labellings of Kg result in the same element of gs.whereas the six labellings of P3 yield three distinct labelled graphs, as shown inFigure0.The numberof distinct labellings ofagiven unlabelled simplegraphG on n vertices is, in fact, n!/aut(G) (Exercise 1.2.15). Consequently, aut(G) = 2()?16 1 Graphs rotational symmetry), as are the five vertices of the inner pentagon. The third drawing exhibits six similar vertices (under reflective or rotational symmetry), namely the vertices of the outer hexagon. Combining these two observations, we conclude that all ten vertices of the Petersen graph are similar, and thus that the graph is vertex-transitive. Fig. 1.9. Three drawings of the Petersen graph We denote the set of all automorphisms of a graph G by Aut(G), and their number by aut(G). It can be verified that Aut(G) is a group under the operation of composition (Exercise 1.2.9). This group is called the automorphism group of G. The automorphism group of Kn is the symmetric group Sn, consisting of all permutations of its vertex set. In general, for any simple graph G on n vertices, Aut(G) is a subgroup of Sn. For instance, the automorphism group of Cn is Dn, the dihedral group on n elements (Exercise 1.2.10). Labelled Graphs As we have seen, the edge set E of a simple graph G = (V,E) is usually considered to be a subset of V 2  , the set of all 2-subsets of V ; edge labels may then be omitted in drawings of such graphs. A simple graph whose vertices are labelled, but whose edges are not, is referred to as a labelled simple graph. If |V | = n, there are 2( n 2) distinct subsets of V 2  , so 2( n 2) labelled simple graphs with vertex set V . We denote by Gn the set of labelled simple graphs with vertex set V := {v1,v2,...,vn}. The set G3 is shown in Figure 1.10. A priori, there are n! ways of assigning the labels v1,v2,...,vn to the vertices of an unlabelled simple graph on n vertices. But two of these will yield the same labelled graph if there is an automorphism of the graph mapping one labelling to the other. For example, all six labellings of K3 result in the same element of G3, whereas the six labellings of P3 yield three distinct labelled graphs, as shown in Figure 1.10. The number of distinct labellings of a given unlabelled simple graph G on n vertices is, in fact, n!/aut(G) (Exercise 1.2.15). Consequently, G n! aut(G) = 2( n 2)