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 (under1.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 vertex￾transitive. 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