1.2Isomorphismsand Automorphisms13GHHFig. 1.6. Isomorphic graphsInordertoshowthattwograstindicateasarophism between them. The pair of mappings (,) defined by(abcd)6123e4e5e6A:-Φ:=(f3f4f1fefsf2023is an isomorphism between the graphs G and H in Figure 1.6.In the case of simple graphs, the definition of isomorphism can be stated moreconcisely,becauseif (,)is an isomorphism between simplegraphs G and H,themapping is completely determined by ; indeed, (e) = e(u)e(u) for any edgee = uu of G. Thus one may define an isomorphism between two simple graphs Gand H as a bijection : V(G) - V(H) which preserves adjacency (that is, thevertices u and u are adjacent in G if and only if their images e(u) and d(u) areadjacent in H).Consider, for example, the graphs G and H in Figure 1.7.HFig. 1.7. Isomorphic simple graphsThe mapping(123456)9:-(bdfcea)is an isomorphism between G and H, as is1.2 Isomorphisms and Automorphisms 13 a b d c e1 e2 e3 e4 e5 e6 G x x y z y w z w f1 f1 f2 f2 f3 f3 f4 f4 f5 f5 f6 f6 H H Fig. 1.6. Isomorphic graphs In order to show that two graphs are isomorphic, one must indicate an isomor￾phism between them. The pair of mappings (θ,φ) defined by θ :=  abcd wzyx  φ :=  e1 e2 e3 e4 e5 e6 f3 f4 f1 f6 f5 f2  is an isomorphism between the graphs G and H in Figure 1.6. In the case of simple graphs, the definition of isomorphism can be stated more concisely, because if (θ,φ) is an isomorphism between simple graphs G and H, the mapping φ is completely determined by θ; indeed, φ(e) = θ(u)θ(v) for any edge e = uv of G. Thus one may define an isomorphism between two simple graphs G and H as a bijection θ : V (G) → V (H) which preserves adjacency (that is, the vertices u and v are adjacent in G if and only if their images θ(u) and θ(v) are adjacent in H). Consider, for example, the graphs G and H in Figure 1.7. 1 23 45 6 a b c e d f G H Fig. 1.7. Isomorphic simple graphs The mapping θ :=  123456 bdfcea  is an isomorphism between G and H, as is