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