1.2IsomorphismsandAutom19lorphisms(6)e(a)Fig. 1.12. Determine the orbits of these graphs (Exercise 1.2.13)1.2.14a) Show that there is no asymmetric simple graph on five or fewer verticesb) For each n ≥ 6, find an asymmetric simple graph on n vertices1.2.15 Let G and H be isomorphic members of gn, let be an isomorphismbetween G and H,and let αbean automorphism of Ga) Show that ea is an isomorphism between G and Hb) Deduce that the set of all isomorphisms between G and H is the coset Aut(G)ofAut(G))Deduce that the numberof labelled graphs isomorphic toG is equal ton!/aut(G)d) Erdos and Renyi (1963) have shown that almost all simple graphs are asym-metric (that is,theproportion of silplegraphs onnvertices that areasymetric tends to one as n tends to infinity). Using this fact, deduce from (c)that the number of unlabelled graphs on n vertices is asymptotically equal to2(2) /n!(G. POLYA)1.2.16 SELF-COMPLEMENTARY GRAPHA simple graph is self-complementary if it is isomorphic to its complement. Showthat:each of the graphs Pa and C (shown in )3b) every self-complementary graph is connectedc) if G is self-complementary, then n = 0, 1 (mod 4)d) every self-complementary graph on 4k + 1 vertices has a vertex of degree 2k1.2.17EDGE-TRANSITIVE GRAPHA simple graph is edqe-transitiue if.for any two edges uv and ry.there is anautomorphism Q such that a(u)a(v) = ry.a) Find a graph which is vertex-transitive but not edge-transitiveb) Show that any graph without isolated vertices which is edge-transitive but not(E. DAUBER)vertex-transitive is bipartite.1.2 Isomorphisms and Automorphisms 19 (a) (b) (c) Fig. 1.12. Determine the orbits of these graphs (Exercise 1.2.13) 1.2.14 a) Show that there is no asymmetric simple graph on five or fewer vertices. b) For each n ≥ 6, find an asymmetric simple graph on n vertices. ————— ————— 1.2.15 Let G and H be isomorphic members of Gn, let θ be an isomorphism between G and H, and let α be an automorphism of G. a) Show that θα is an isomorphism between G and H. b) Deduce that the set of all isomorphisms between G and H is the coset θAut(G) of Aut(G). c) Deduce that the number of labelled graphs isomorphic to G is equal to n!/aut(G). d) Erd˝os and R´enyi (1963) have shown that almost all simple graphs are asym￾metric (that is, the proportion of simple graphs on n vertices that are asym￾metric tends to one as n tends to infinity). Using this fact, deduce from (c) that the number of unlabelled graphs on n vertices is asymptotically equal to 2( n 2)/n! (G. Polya) ´ 1.2.16 Self-Complementary Graph A simple graph is self-complementary if it is isomorphic to its complement. Show that: a) each of the graphs P4 and C5 (shown in Figure 1.3) is self-complementary, b) every self-complementary graph is connected, c) if G is self-complementary, then n ≡ 0, 1 (mod 4), d) every self-complementary graph on 4k + 1 vertices has a vertex of degree 2k. 1.2.17 Edge-Transitive Graph A simple graph is edge-transitive if, for any two edges uv and xy, there is an automorphism α such that α(u)α(v) = xy. a) Find a graph which is vertex-transitive but not edge-transitive. b) Show that any graph without isolated vertices which is edge-transitive but not vertex-transitive is bipartite. (E. Dauber)