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 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 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 auto￾morphism 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