141 Graphs（123456)OacedfbIsomorphic graphs clearly have the same numbers of vertices and edges. Onthe other hand, equality of these parameters does not guarantee isomorphism. Forinstance, the two graphs shown in Figure 1.8 both have eight vertices and twelveedges, but they are not isomorphic. To see this, observe that the graph G has fourmutually nonadjacent vertices, v1, 23, V6, and vs. If there were an isomorphism ebetween G and H, the vertices (ui), e(v3), (v6), and e(us) of H would likewisbemutually nonadjacent.Butit canreadily bechecked that nofourvertices ofHare mutually nonadjacent. We deduce that G and H are not isomorphic.TFig. 1.8. NonisoomorphicgraphsIt is clear from the foregoing discussion that if two graphs are isomorphic, thenthey are either identical or differ merely in the names of their vertices and edgesand thus have the same structure. Because it is primarily in structural propertiesthat we are interested, we often omit labels when drawing graphs; formally, we maydefine an unlabelled graph as a representative ofan equivalence class of isomorphicgraphs. We assign labels to vertices and edges in a graph mainly for the purposeof refering to them (in proofs, for instance).Up to isomorphism, there is just one complete graph on n vertices, denoted KnSimilarly, given two positive integers m and n, there is a unique complete bipartitegraph with parts of sizes m and n (again, up to isomorphism), denoted Km.nIn this notation, the graphs in Figure 1.2 are Ks, K3.3, and Ki,5, respectively.Likewise, for any positive integer n, there is a unique path on n vertices and aunique cycle on n vertices.These graphs are denoted Pn and Cn,respectively.Thegraphs depicted in Figure 1.3 are Pr and Cs.TESTING FOR ISOMORPHISMGiven two graphs on n vertices, it is certainly possible in principle to determinwhethertheyFor instance, if G and H arple,onecouldjustconsider each of the n! bijections between V(G) and V(H) in turn, and check
14 1 Graphs θ := 123456 acedfb Isomorphic graphs clearly have the same numbers of vertices and edges. On the other hand, equality of these parameters does not guarantee isomorphism. For instance, the two graphs shown in Figure 1.8 both have eight vertices and twelve edges, but they are not isomorphic. To see this, observe that the graph G has four mutually nonadjacent vertices, v1, v3, v6, and v8. If there were an isomorphism θ between G and H, the vertices θ(v1), θ(v3), θ(v6), and θ(v8) of H would likewise be mutually nonadjacent. But it can readily be checked that no four vertices of H are mutually nonadjacent. We deduce that G and H are not isomorphic. v1 v2 v1 v2 v3 v3 v4 v4 v5 v6 v5 v6 v7 v7 v8 v8 G H Fig. 1.8. Nonisomorphic graphs It is clear from the foregoing discussion that if two graphs are isomorphic, then they are either identical or differ merely in the names of their vertices and edges, and thus have the same structure. Because it is primarily in structural properties that we are interested, we often omit labels when drawing graphs; formally, we may define an unlabelled graph as a representative of an equivalence class of isomorphic graphs. We assign labels to vertices and edges in a graph mainly for the purpose of referring to them (in proofs, for instance). Up to isomorphism, there is just one complete graph on n vertices, denoted Kn. Similarly, given two positive integers m and n, there is a unique complete bipartite graph with parts of sizes m and n (again, up to isomorphism), denoted Km,n. In this notation, the graphs in Figure 1.2 are K5, K3,3, and K1,5, respectively. Likewise, for any positive integer n, there is a unique path on n vertices and a unique cycle on n vertices. These graphs are denoted Pn and Cn, respectively. The graphs depicted in Figure 1.3 are P4 and C5. Testing for Isomorphism Given two graphs on n vertices, it is certainly possible in principle to determine whether they are isomorphic. For instance, if G and H are simple, one could just consider each of the n! bijections between V (G) and V (H) in turn, and check
1.2 Isomorphisms and Automorphisms15whether it is an isomorphism between the two graphs. If the ggraphs happen to beisomorphic,an isomorphismmight (with luck)befound quickly.Ontheotherhand,if they are not isomorphic, one would need to check all n! bijections to discoverthis fact. Unfortunately, even for moderately small values of n (such as n = 100),the number n!is unmanageably large (indeed. larger than the number of particles),so this brute force'approach is not feasible. Of coursese.ifthein the universgraphs are not regular,the number ofbijections to be checked will be smaller,as anmap each vertex to a vertex ofthe same degree (Exercise 1.2.la).O1115Nonetheless, except in particular cases, this restriction does not serve to reducetheir number sufficiently. Indeed, no eficient generally applicable procedure fortesting isomorphism is known.However, by employing powerful group-theoreticmethods, Luks (1982) devised an efficient isomorphism-testing algorithm for cubicgraphs and, more generally, for graphs of bounded maximum degree.There is another important matter related to algorithmic questions such asgraph isomorphism. Suppose that two simple graphs G and H are isomorphicIt might not be easy to find an isomorphism between them, but once such an has been found,it isasimplematter toverifythat is indeed ansomorDhneed merely check that, for each of the () pairs uu of verticeorphsofG, wuE(C) if and only ife(u)e(o)E(H). On the other hand, ifG and Hone verify this fact, short of checking allhappennottobeisomorphic,howcanpossible bijections between V(G) and V(H)? In certain cases, one might be able toshow that G and H are not isomorphic by isolating some structural property of Gthat is not shared by H, as we did for the graphs G and H of Figure 1.8. However, ingeneral,verifying that two nonisomorphicgraphs are indeed not isomorphic seemsto be just as hard as determining in the first place whether they are isomorphic ornot.AUTOMORPHISMSAn automorphism of a graph is an isomorphism of the graph to itself. In the casof a simple graph, an automorphism is just a permutation aα of its vertex set whichpreserves adjacency: if uu is an edge then so is a(u)a(u)The automorphisms of a graph reflect its syimetries.Forexample,if uancare two vertices of a simple graph, and if there is an automorphism whichmaps u to u, then u and u are alike in the graph, and are referred to as similanvertices. Graphs in which all vertices are similar, such as the complete graphKn, the complete bipartite graph Kn,n and the n-cube Qn, are called vertertransitive. Graphs in which no two vertices are similar are called asymmetric,these are the graphs which have only the identity permutation as automorphism(see Exercise 1.2.14)Particular drawings of a graph may often be used to display its symmetriesAs an example, consider the three drawings shown in Figure 1.9 of the Petersengraphgraphwhichturnsoutohavemanyspcialroperties.(Weleaveitan exercise (1.2.5) that they are indeed drawings of one and the same graph.) Thefirst drawing shows that the five vertices of the outer pentagon are similar (under
1.2 Isomorphisms and Automorphisms 15 whether it is an isomorphism between the two graphs. If the graphs happen to be isomorphic, an isomorphism might (with luck) be found quickly. On the other hand, if they are not isomorphic, one would need to check all n! bijections to discover this fact. Unfortunately, even for moderately small values of n (such as n = 100), the number n! is unmanageably large (indeed, larger than the number of particles in the universe!), so this ‘brute force’ approach is not feasible. Of course, if the graphs are not regular, the number of bijections to be checked will be smaller, as an isomorphism must map each vertex to a vertex of the same degree (Exercise 1.2.1a). Nonetheless, except in particular cases, this restriction does not serve to reduce their number sufficiently. Indeed, no efficient generally applicable procedure for testing isomorphism is known. However, by employing powerful group-theoretic methods, Luks (1982) devised an efficient isomorphism-testing algorithm for cubic graphs and, more generally, for graphs of bounded maximum degree. There is another important matter related to algorithmic questions such as graph isomorphism. Suppose that two simple graphs G and H are isomorphic. It might not be easy to find an isomorphism between them, but once such an isomorphism θ has been found, it is a simple matter to verify that θ is indeed an isomorphism: one need merely check that, for each of the n 2 pairs uv of vertices of G, uv ∈ E(G) if and only if θ(u)θ(v) ∈ E(H). On the other hand, if G and H happen not to be isomorphic, how can one verify this fact, short of checking all possible bijections between V (G) and V (H)? In certain cases, one might be able to show that G and H are not isomorphic by isolating some structural property of G that is not shared by H, as we did for the graphs G and H of Figure 1.8. However, in general, verifying that two nonisomorphic graphs are indeed not isomorphic seems to be just as hard as determining in the first place whether they are isomorphic or not. Automorphisms An automorphism of a graph is an isomorphism of the graph to itself. In the case of a simple graph, an automorphism is just a permutation α of its vertex set which preserves adjacency: if uv is an edge then so is α(u)α(v). The automorphisms of a graph reflect its symmetries. For example, if u and v are two vertices of a simple graph, and if there is an automorphism α which maps u to v, then u and v are alike in the graph, and are referred to as similar vertices. Graphs in which all vertices are similar, such as the complete graph Kn, the complete bipartite graph Kn,n and the n-cube Qn, are called vertextransitive. Graphs in which no two vertices are similar are called asymmetric; these are the graphs which have only the identity permutation as automorphism (see Exercise 1.2.14). Particular drawings of a graph may often be used to display its symmetries. As an example, consider the three drawings shown in Figure 1.9 of the Petersen graph, a graph which turns out to have many special properties. (We leave it as an exercise (1.2.5) that they are indeed drawings of one and the same graph.) The first drawing shows that the five vertices of the outer pentagon are similar (under
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)
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.7
1.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) degree 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
181 GraphsFig. 1.11. Nonisoorphic graphsb) the number of automorphisms of each of these graphs.+1.2.5 Show that the three graphs in Figure 1.9 are isomorphic.1.2.6 Drawa) all the labelled simple graphs on four vertices.b) all the unlabelled simple graphs on four verticesc) all the unlabelled simple cubic graphs on eight or fewer vertices1.2.7 Show that the n-cube Qn and the boolean lattice BLn (defined in Exer-cises 1.1.7 and 1.1.8) are isomorphic.1.2.8 Show that two simple graphs G and H are isomorphic if and only if thereexists a permutation matrix P such that AH = PAcPt1.2.9 Show that Aut(G) is a group under the operation of composition.1.2.10a) Show that, for n ≥2, Aut(P.) = S2 and Aut(Cn) = Dn, the dihedral group onn elements (where denotes isomorphism of groups; see, for example, Herstein(1996).b) Determine the automorphism group of the complete bipartite graph Km,n1.2.11 Show that, for any simple graph G, Aut(G) = Aut(G)1.2.12 Consider the subgroup I of S3 with elements (1)(2)(3), (123), and (132)a) Show that there is no simple graph whose automorphism group is Fb) Find a simple graph whose automorphism group is isomorphic to I.(Frucht (1938) showed that every abstract group is isomorphic to the automorphismgroup of somesimplegraph.)1.2.13ORBITS OFAGRAPHa) Show that similarity is an equivalence relation on the vertex set of a graph.b) The equivalence classes with respect to similarity are called the orbits of thegraph. Determine the orbits of the graphs in Figure 1.12
18 1 Graphs Fig. 1.11. Nonisomorphic graphs b) the number of automorphisms of each of these graphs. 1.2.5 Show that the three graphs in Figure 1.9 are isomorphic. 1.2.6 Draw: a) all the labelled simple graphs on four vertices, b) all the unlabelled simple graphs on four vertices, c) all the unlabelled simple cubic graphs on eight or fewer vertices. 1.2.7 Show that the n-cube Qn and the boolean lattice BLn (defined in Exercises 1.1.7 and 1.1.8) are isomorphic. 1.2.8 Show that two simple graphs G and H are isomorphic if and only if there exists a permutation matrix P such that AH = PAGPt . 1.2.9 Show that Aut(G) is a group under the operation of composition. 1.2.10 a) Show that, for n ≥ 2, Aut(Pn) ∼= S2 and Aut(Cn) = Dn, the dihedral group on n elements (where ∼= denotes isomorphism of groups; see, for example, Herstein (1996)). b) Determine the automorphism group of the complete bipartite graph Km,n. 1.2.11 Show that, for any simple graph G, Aut(G) = Aut(G). 1.2.12 Consider the subgroup Γ of S3 with elements (1)(2)(3), (123), and (132). a) Show that there is no simple graph whose automorphism group is Γ. b) Find a simple graph whose automorphism group is isomorphic to Γ. (Frucht (1938) showed that every abstract group is isomorphic to the automorphism group of some simple graph.) 1.2.13 Orbits of a Graph a) Show that similarity is an equivalence relation on the vertex set of a graph. b) The equivalence classes with respect to similarity are called the orbits of the graph. Determine the orbits of the graphs in Figure 1.12