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 asymmetric (that is, the proportion of simple graphs on n vertices that are asymmetric 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)
201 Graphs1.2.18 THE FOLKMAN GRAPHa)Shorin Figure 1.13a is edge-tthat the graplotvertextransitive(b)CFig. 1.13. Cohe Folkman graphb) The Folkman graph, depicted in Figure 1.13b, is the 4-regular graph obtainedfrom thegraph of Figure 1.13aby replacing eachvertex of degree eight bytwo vertices of degree four, both of which have the same four neighbours as uShow that the Folkman graph is edge-transitive but not vertex-transitive.(J. FOLKMAN)1.2.19 GENERALIZED PETERSEN GRAPHLet k and n be positive integers, with n > 2k. The generalized Petersen graphPk.n is the simple graph with vertices i,12,..*,n,i.y2..Yn, and edges1,yiyi+k,Fiyi,1≤i≤ n, indices being taken modulo n. (Note that P2.5:TisthePetersengraph.)Drawe graphs P2.7 and Ps.shob)Which of these two graphs are vertIareedge-transitive?1.2.20 Show that if G is simple and the eigenvalues of A are distinct, then eautomorphismofGisof orderoneortwo.(A. MOwSHOwITz)1.3 Graphs Arising from Other StructuresAsremarkedearlier,interesting graphs can often beconstructedfrom geometricand algebraic objects. Such constructions are often quite straightforward, but insome instances they rely on experience and insight
20 1 Graphs 1.2.18 The Folkman Graph a) Show that the graph shown in Figure 1.13a is edge-transitive but not vertextransitive. (a) (b) Fig. 1.13. Construction of the Folkman graph b) The Folkman graph, depicted in Figure 1.13b, is the 4-regular graph obtained from the graph of Figure 1.13a by replacing each vertex v of degree eight by two vertices of degree four, both of which have the same four neighbours as v. Show that the Folkman graph is edge-transitive but not vertex-transitive. (J. Folkman) 1.2.19 Generalized Petersen Graph Let k and n be positive integers, with n > 2k. The generalized Petersen graph Pk,n is the simple graph with vertices x1,x2,...,xn,y1,y2,...,yn, and edges xixi+1,yiyi+k,xiyi, 1 ≤ i ≤ n, indices being taken modulo n. (Note that P2,5 is the Petersen graph.) a) Draw the graphs P2,7 and P3,8. b) Which of these two graphs are vertex-transitive, and which are edge-transitive? 1.2.20 Show that if G is simple and the eigenvalues of A are distinct, then every automorphism of G is of order one or two. (A. Mowshowitz) 1.3 Graphs Arising from Other Structures As remarked earlier, interesting graphs can often be constructed from geometric and algebraic objects. Such constructions are often quite straightforward, but in some instances they rely on experience and insight
1.3GraphsArisingfromOtherStructures21POLYHEDRAL GRAPHSA polyhedral graph is the 1-skeleton of a polyhedron, that is, the graph whovertices and edges are just the vertices and edges of the polyhedron, with thesame incidence relation.In particular,the five platonic solids (the tetrahedronthe cube, the octahedron, the dodecahedron, and the icosahedron) give rise to thefive platonic graphs shown in Figure 1.14. For classical polyhedra such as these,we give the graph the same nameleasthepolyhedron from whichitisderivedAA(a)(c)(d)(e)Fig. 1.14. The five platonic graphs: (a) the tetrahedron, (b) the octahedron, (c) thecube, (d) the dodecahedron, (e) the icosahedronSET SYSTEMS AND HYPERGRAPHSered pair (VF),where V is a set of elements and F iA setsystemisaoa family of subsets of V. Note that when F consists of pairs of elements of Vthe set system (V, F) is a loopless graph. Thus set systems can be thought of asgeneralizations of graphs, and are usuallyreferred to as hypergraphs,particularlywhen one seeks to extend properties of graphs to set systems (see Berge (1973).The elements of V are then called the uertices of the hypergraph, and the elementsof F its edges or hyperedges. A hypergraph is k-uniform if each edge is a k-set (a setof k elements). As we show below, set systems give rise to graphs in two principalways incidence graphs and intersection graphsMany interesting examples of hypergraphs are provided by geometric configurations. A geometric configuration (P,C) consists of a finite set P of elements
1.3 Graphs Arising from Other Structures 21 Polyhedral Graphs A polyhedral graph is the 1-skeleton of a polyhedron, that is, the graph whose vertices and edges are just the vertices and edges of the polyhedron, with the same incidence relation. In particular, the five platonic solids (the tetrahedron, the cube, the octahedron, the dodecahedron, and the icosahedron) give rise to the five platonic graphs shown in Figure 1.14. For classical polyhedra such as these, we give the graph the same name as the polyhedron from which it is derived. (a) (b) (c) (d) (e) Fig. 1.14. The five platonic graphs: (a) the tetrahedron, (b) the octahedron, (c) the cube, (d) the dodecahedron, (e) the icosahedron Set Systems and Hypergraphs A set system is an ordered pair (V, F), where V is a set of elements and F is a family of subsets of V . Note that when F consists of pairs of elements of V , the set system (V, F) is a loopless graph. Thus set systems can be thought of as generalizations of graphs, and are usually referred to as hypergraphs, particularly when one seeks to extend properties of graphs to set systems (see Berge (1973)). The elements of V are then called the vertices of the hypergraph, and the elements of F its edges or hyperedges. A hypergraph is k-uniform if each edge is a k-set (a set of k elements). As we show below, set systems give rise to graphs in two principal ways: incidence graphs and intersection graphs. Many interesting examples of hypergraphs are provided by geometric configurations. A geometric configuration (P,L) consists of a finite set P of elements
221 Graphscalled points, andafinitefamily ofsubsets of Pcaled lines, withthe propertythat at most one line contains any given pair of points. Two classicalexamplesof geometric configurations are the Fano plane and the Desargues configurationThese two configurations are shown in Figure 1.15. In both cases, each line consistsof three points. These configurations thus give rise to 3-uniform hypergraphs; theFano hypergraph has seven vertices and seven edges, the Desargues hypergraph tenvertices and ten edgesa(a)(6)Fig. 1.15. (a) The Fano plane, and (b) the DesargueconfigurationThe Fano plane is the simplest of an important family of geometric configu-rations.theprojectiveplanes (see Exercise 1.3.13).The Desargues configurationarises from a well-known theorem in projective geometry. Other examples of interesting geometric configurations are described in Coxeter (1950)and Godsil andRoyle (2001).INCIDENCE GRAPHSA natural graph associated with a set system H -(V,F) is the bipartite graphGV.Flwherew EV and FEFare adjacent if EF.This bipartitegraph G iscalled the incidence graph of the set system H, and the bipartite adjacency matrixof Gthe incidencematrirof H:theseare simply alternativeways of representing aset system. Incidence graphs of geometric configurations often give rise to interesting bipartite graphs; in this context, the incidence graph is sometimes called theLevi graph of thconfiguration. The inciclence graph of the Fano plane is shownin Figure 1.16. This graph is known as the Heawood graph.INTERSECRAPHWith each set system (V,F) one may associate its intersection graph. This is thegraph whose vertex set is F, two sets in F being adjacent if their intersection isnonempty. For instance, when V is the vertex set of a simple graph G and F :=- E
22 1 Graphs called points, and a finite family L of subsets of P called lines, with the property that at most one line contains any given pair of points. Two classical examples of geometric configurations are the Fano plane and the Desargues configuration. These two configurations are shown in Figure 1.15. In both cases, each line consists of three points. These configurations thus give rise to 3-uniform hypergraphs; the Fano hypergraph has seven vertices and seven edges, the Desargues hypergraph ten vertices and ten edges. 1 2 3 4 5 6 7 a1 b1 c1 a2 b2 c2 a3 b3 c3 d (a) (b) Fig. 1.15. (a) The Fano plane, and (b) the Desargues configuration The Fano plane is the simplest of an important family of geometric configurations, the projective planes (see Exercise 1.3.13). The Desargues configuration arises from a well-known theorem in projective geometry. Other examples of interesting geometric configurations are described in Coxeter (1950) and Godsil and Royle (2001). Incidence Graphs A natural graph associated with a set system H = (V, F) is the bipartite graph G[V, F], where v ∈ V and F ∈ F are adjacent if v ∈ F. This bipartite graph G is called the incidence graph of the set system H, and the bipartite adjacency matrix of G the incidence matrix of H; these are simply alternative ways of representing a set system. Incidence graphs of geometric configurations often give rise to interesting bipartite graphs; in this context, the incidence graph is sometimes called the Levi graph of the configuration. The incidence graph of the Fano plane is shown in Figure 1.16. This graph is known as the Heawood graph. Intersection Graphs With each set system (V, F) one may associate its intersection graph. This is the graph whose vertex set is F, two sets in F being adjacent if their intersection is nonempty. For instance, when V is the vertex set of a simple graph G and F := E
1.3GraphsArisingfromOtherStructures23Fig. 1.16. The incidencee graph of the Fano plane: the Heawood graphthe edge set of G, the intersection graph of (V, F) has as vertices the edges of Gtwo edges being adiacent if they have an end in common. For historical reasonsthis graph is known as the line graph of G and denoted L(G). Figure 1.17 depictsa graph and its line graph.04GL(G)Fig. 1.17. A graph and its line graphIt can be shown that the intersection graph of the Desargues configuration isisomorphic to the line graph of Ks, which in turn is isomorphic to the complementof the Petersen graph (Exercise 1.3.2). As for the Fano plane, its intersection graphis isomorphic to Kz, because any two of its seven lines have a point in common.The definition of the line graph L(G) may be extended to all loopless graphsG as being the graph with vertex set E in which two vertices are joined by just asedges as theiends inGerofWhen V-R and F is a set of closed intervals of R.theintaph.o(V,F) is called an interual graph. Examples of practical situations which give riseto interval graphs can be found in the book by Berge (1973). Berge even wrote adetective story whose resolution relies on the theory of interval graphs; see Berge(1995).It should be evident from the above examples that graphs are implicit in awide variety of structures. Many such graphs are not only interesting in their ownright but also serve to provide insight into the structures from which they arise
1.3 Graphs Arising from Other Structures 23 1234567 124 235 346 457 156 267 137 Fig. 1.16. The incidence graph of the Fano plane: the Heawood graph the edge set of G, the intersection graph of (V, F) has as vertices the edges of G, two edges being adjacent if they have an end in common. For historical reasons, this graph is known as the line graph of G and denoted L(G). Figure 1.17 depicts a graph and its line graph. 1 2 4 3 12 24 23 34 G L(G) Fig. 1.17. A graph and its line graph It can be shown that the intersection graph of the Desargues configuration is isomorphic to the line graph of K5, which in turn is isomorphic to the complement of the Petersen graph (Exercise 1.3.2). As for the Fano plane, its intersection graph is isomorphic to K7, because any two of its seven lines have a point in common. The definition of the line graph L(G) may be extended to all loopless graphs G as being the graph with vertex set E in which two vertices are joined by just as many edges as their number of common ends in G. When V = R and F is a set of closed intervals of R, the intersection graph of (V, F) is called an interval graph. Examples of practical situations which give rise to interval graphs can be found in the book by Berge (1973). Berge even wrote a detective story whose resolution relies on the theory of interval graphs; see Berge (1995). It should be evident from the above examples that graphs are implicit in a wide variety of structures. Many such graphs are not only interesting in their own right but also serve to provide insight into the structures from which they arise