241 GraphsExercises1.3.1a) Show that the graph in Figure 1.18 is isomorphic to the Heawood graph (Figure1.16).Fig. 1.18. Another drawing of the Heawood graphb) Deduce that the Heawood graph is vertex-transitive.1.3.2 Show that the fllowing three graphs are isomorphic:D the intersection graph of the Desargues configuration,the line graph of Ks the complement of the Petersen graph.1.3.3 Showthat the line graph of K3.3 is self-complement:a1.3.4 Show that neither of the graphs displayed in Figure 1.19 is a line graph1.3.5 Let H := (V, F) be a hypergraph. The number of edges incident with aex u of H is its degree, denoted d(u). A degree sequence of H is a vectorord :=(d(u) :we V). Let M be the incidence matrix of H and d the correspondingdegree sequence of H. Show that the sum of the columns of M is equal to d.1.3.6 Let H :-- (V, F) be a hypergraph. For u e V, let F, denote the set of edgesof H incident to u. The dual of H is the hypergraph H* whose vertex set is F andwhose edges are the sets Fu, u e V.Fig. 1.19. Two graphs that are not line graphs
24 1 Graphs Exercises 1.3.1 a) Show that the graph in Figure 1.18 is isomorphic to the Heawood graph (Figure 1.16). Fig. 1.18. Another drawing of the Heawood graph b) Deduce that the Heawood graph is vertex-transitive. 1.3.2 Show that the following three graphs are isomorphic: the intersection graph of the Desargues configuration, the line graph of K5, the complement of the Petersen graph. 1.3.3 Show that the line graph of K3,3 is self-complementary. 1.3.4 Show that neither of the graphs displayed in Figure 1.19 is a line graph. 1.3.5 Let H := (V, F) be a hypergraph. The number of edges incident with a vertex v of H is its degree, denoted d(v). A degree sequence of H is a vector d := (d(v) : v ∈ V ). Let M be the incidence matrix of H and d the corresponding degree sequence of H. Show that the sum of the columns of M is equal to d. 1.3.6 Let H := (V, F) be a hypergraph. For v ∈ V , let Fv denote the set of edges of H incident to v. The dual of H is the hypergraph H∗ whose vertex set is F and whose edges are the sets Fv, v ∈ V . Fig. 1.19. Two graphs that are not line graphs
251.3 Graphs Arising from Other Structuresa) How are the incidence graphs of H and H* related?b) Show that the dual of H* is isomorphic to H.c) A hypergraph is self-dual if it is isomorphic to its dual. Show that the Fanoand Desargues hypergraphs are self-dual1.3.7HELLYPROPERTYAfamily of sets has the Helly Property ifthe members ofeach pairwise intersectingsubfamily have an element in commora)Showthatthefamily of closed intervals on thereal linehas theHellyProperty(E. HELLY)b) Deduce that the graph in Figure 1.20 is not an interval graph.Fig. 1.20. A graph that is not an interval graph1.3.8 KNESER GRAPHLet m and n be positive integers, where n > 2m. The Kneser graph KGm,n isthe graph whose vertices are the m-subsets of an n-set S, two such subsets beingadjacent if and only if their intersection is empty. Show that:a) KGi,n= Kn, n ≥3,b) KG2.n is isomorphic to the complement of L(Kn), n ≥ 51.3.9 Let G be a simple graph with incidence matrix M.a) Show that the adjacency matrix ofits line graph L(G) is M'M-2I, whereIisthem xmidentitymatrix.b) Using the fact that M'Mis positive-semidefinite, deduce that:i) each eigenvalue of L(G) is at least2,ii) if the rank of M is less than m, then -2 is an eigenvalue of L(G)-1.3.10a) Consider the following two matrices B and C, where is an indeterminate, Mis an arbitrary n x m matrix, and I is an identity matrix of the appropriatedimension.B - [M MC.- [-M]
1.3 Graphs Arising from Other Structures 25 a) How are the incidence graphs of H and H∗ related? b) Show that the dual of H∗ is isomorphic to H. c) A hypergraph is self-dual if it is isomorphic to its dual. Show that the Fano and Desargues hypergraphs are self-dual. 1.3.7 Helly Property A family of sets has the Helly Property if the members of each pairwise intersecting subfamily have an element in common. a) Show that the family of closed intervals on the real line has the Helly Property. (E. Helly) b) Deduce that the graph in Figure 1.20 is not an interval graph. Fig. 1.20. A graph that is not an interval graph 1.3.8 Kneser Graph Let m and n be positive integers, where n > 2m. The Kneser graph KGm,n is the graph whose vertices are the m-subsets of an n-set S, two such subsets being adjacent if and only if their intersection is empty. Show that: a) KG1,n ∼= Kn, n ≥ 3, b) KG2,n is isomorphic to the complement of L(Kn), n ≥ 5. 1.3.9 Let G be a simple graph with incidence matrix M. a) Show that the adjacency matrix of its line graph L(G) is Mt M − 2I, where I is the m × m identity matrix. b) Using the fact that Mt M is positive-semidefinite, deduce that: i) each eigenvalue of L(G) is at least −2, ii) if the rank of M is less than m, then −2 is an eigenvalue of L(G) . ————— ————— 1.3.10 a) Consider the following two matrices B and C, where x is an indeterminate, M is an arbitrary n × m matrix, and I is an identity matrix of the appropriate dimension. B := I M Mt xI C := xI −M 0 I
261 GraphsBy equating the determinants of BC and CB, derive the identitydet(rI - M'M) = rm-n det(zI- MMt)b) Let G be a simple k-regular graph with k ≥ 2. By appealing to Exercise 1.3.9and using the above identity, establish the following relationship between thecharacteristic polynomials of L(G) and G.det(AL(G) -I) =(-1)mn(r + 2)m-n det(AG -( + 2 - k)I)c) Deduce that:i) to each eigenvalue入/-k of G, there corresponds an eigenvalue +k2of L(G), with the same multiplicityi) -2 is an eigenvalue of L(G) with multiplicity m - n + r, where r is themultiplicity of the eigenvalue -k of G. (If -k is not an eigenvalue of Gthen r = 0.)(H. SACHS)1.3.11a) Using Exercises 1.1.22 and 1.3.10, show that the eigenvalues of L(Ks) are(6, 1,1,1,1, -2, -2, -2, -2, -2)b) Applying Exercise 1.1.23, deduce that the Petersen graph has eigenvalues(3, 1, 1,1, 1, 1, 2, 2, 2, 2)1.3.12 SPERNER'S LEMMALet T be a triangle in the plane. A subdivision of T into triangles is simplicial ifany two of the triangles which intersect have either a vertex or an edge in commonler an arbitrary simplicial subdivision of T into triangles. Assign the coloursred, blue, and green to the vertices of these triangles in such a way that eachcolour ismissingfrom one sideofTbut appears on the other twosides.(Thus, inparticular, the vertices of T are assigned the colours red, blue, and green in someorder.)a) Show that the number of triangles in the subdivision whose vertices receive allthree colours is odd.(E.SPERNER)b) Deduce that there is always at least one such triangle(Sperner's Lemma, generalized to n-dimensional simplices, is the key ingredient inaproof ofBrouwer'sFixedPointTheorem:every continuomapping of a closedn-disc to itself has a fired point: see Bondy and Murty (1976).)1.3.13FINITE PROJECTIVE PLANEA finite projective plane is a geometric configuration (P,C) in which:i)anytwopointslieonexactlyonelineii) any two lines meet in exactly one point
26 1 Graphs By equating the determinants of BC and CB, derive the identity det(xI − Mt M) = xm−n det(xI − MMt ) b) Let G be a simple k-regular graph with k ≥ 2. By appealing to Exercise 1.3.9 and using the above identity, establish the following relationship between the characteristic polynomials of L(G) and G. det(AL(G) − xI)=(−1)m−n(x + 2)m−n det(AG − (x + 2 − k)I) c) Deduce that: i) to each eigenvalue λ = −k of G, there corresponds an eigenvalue λ + k − 2 of L(G), with the same multiplicity, ii) −2 is an eigenvalue of L(G) with multiplicity m − n + r, where r is the multiplicity of the eigenvalue −k of G. (If −k is not an eigenvalue of G then r = 0.) (H. Sachs) 1.3.11 a) Using Exercises 1.1.22 and 1.3.10, show that the eigenvalues of L(K5) are (6, 1, 1, 1, 1, −2, −2, −2, −2, −2) b) Applying Exercise 1.1.23, deduce that the Petersen graph has eigenvalues (3, 1, 1, 1, 1, 1, −2, −2, −2, −2) 1.3.12 Sperner’s Lemma Let T be a triangle in the plane. A subdivision of T into triangles is simplicial if any two of the triangles which intersect have either a vertex or an edge in common. Consider an arbitrary simplicial subdivision of T into triangles. Assign the colours red, blue, and green to the vertices of these triangles in such a way that each colour is missing from one side of T but appears on the other two sides. (Thus, in particular, the vertices of T are assigned the colours red, blue, and green in some order.) a) Show that the number of triangles in the subdivision whose vertices receive all three colours is odd. (E. Sperner) b) Deduce that there is always at least one such triangle. (Sperner’s Lemma, generalized to n-dimensional simplices, is the key ingredient in a proof of Brouwer’s Fixed Point Theorem: every continuous mapping of a closed n-disc to itself has a fixed point; see Bondy and Murty (1976).) 1.3.13 Finite Projective Plane A finite projective plane is a geometric configuration (P,L) in which: i) any two points lie on exactly one line, ii) any two lines meet in exactly one point
1.3 Graphs Arising from Other Structures27ii) there are four points no three of which lie on a line(Condition (ii) serves only to exclude two trivial configurations- the pencil, inwhich all points are collinear, and the near-pencil, in which all but one of thepoints are collinear.)a) Let (P,C) be a finite projective plane. Show that there is an integer n ≥ 2such that [P| = |C| = n? n + 1, each point lies on n + 1 lines, and each linecontains n+1points (the instance n=2 being the Fano plane).This integern is called the order of the projective plane.b) How many vertices has the incidence graph of a finite projective plane of orderand what are their degrees?1.3.14 Consider thein F3, wherGF(q) and qipower. Define two of these vectors to be equivalentifone is a multiple of theother. One can form a finite projective plane (P, C) of order q by taking as pointsand lines the (q3 - 1)/(q - 1) = q? + q + 1 equivalence classes defined by thisequivalence relation and defining a point (a,b,c) and line (r, y, z) to be incident ifa+by+cz=0 (in GF()).This plane is denoted PG2.ga) Show that PG2.2 is isomorphic to theFano plane.b)ConstructPG2.31.3.15THEDEBRUIJN-ERDOSTHEOREMa) Let G[X,Y] be a bipartite graph, each vertex of which is joined to at leastone, but not all, vertices in the other part. Suppose that d(r) ≥ d(y) for allry E. Show that [Y| ≥ [X], with equality if and only if d(r) = d(y) for allry tEwithreX and yeYb) DeducecethefollowingtheoreLet (P,C) beageometric confguration in which any two points le on exactlyonelineand not all points lie on a single line. Then |C ≥ /P|. Furthermore, ifIC| = |Pl, then (P, C) is either a finite projective plane or a near-pencil(N.G.DE BRUIJN AND P.ERDOS)1.3.16 Show that:a) the line graphs L(Kn), n ≥ 4, and L(Kn,n), n ≥ 2, are strongly regularb) the Shrikhande graph, displayed in Figure 1.21 (where vertices with the sanlabel aretobeidentified),is stronglyregular,withthesameparametersathose of L(K4,4), but is not isomorphic to L(K4.4).1.3.17a) Show that:i) Aut(L(K,))竿 Aut(Kn) for n = 2 and n = 4i) Aut(L(Kn)) = Aut(K,) for nandn>5b) Appealing to Exercises 1.2.11 and 1.3.2, deduce that the automorphism groupof the Petersengraph is isomorphic to the symmetric group Ss
1.3 Graphs Arising from Other Structures 27 iii) there are four points no three of which lie on a line. (Condition (iii) serves only to exclude two trivial configurations — the pencil, in which all points are collinear, and the near-pencil, in which all but one of the points are collinear.) a) Let (P,L) be a finite projective plane. Show that there is an integer n ≥ 2 such that |P| = |L| = n2 + n + 1, each point lies on n + 1 lines, and each line contains n + 1 points (the instance n = 2 being the Fano plane). This integer n is called the order of the projective plane. b) How many vertices has the incidence graph of a finite projective plane of order n, and what are their degrees? 1.3.14 Consider the nonzero vectors in F3, where F = GF(q) and q is a prime power. Define two of these vectors to be equivalent if one is a multiple of the other. One can form a finite projective plane (P,L) of order q by taking as points and lines the (q3 − 1)/(q − 1) = q2 + q + 1 equivalence classes defined by this equivalence relation and defining a point (a,b,c) and line (x,y,z) to be incident if ax + by + cz = 0 (in GF(q)). This plane is denoted PG2,q. a) Show that PG2,2 is isomorphic to the Fano plane. b) Construct PG2,3. 1.3.15 The de Bruijn–Erdos Theorem ˝ a) Let G[X,Y ] be a bipartite graph, each vertex of which is joined to at least one, but not all, vertices in the other part. Suppose that d(x) ≥ d(y) for all xy /∈ E. Show that |Y |≥|X|, with equality if and only if d(x) = d(y) for all xy /∈ E with x ∈ X and y ∈ Y . b) Deduce the following theorem. Let (P,L) be a geometric configuration in which any two points lie on exactly one line and not all points lie on a single line. Then |L| ≥ |P|. Furthermore, if |L| = |P|, then (P,L) is either a finite projective plane or a near-pencil. (N.G. de Bruijn and P. Erdos) ˝ 1.3.16 Show that: a) the line graphs L(Kn), n ≥ 4, and L(Kn,n), n ≥ 2, are strongly regular, b) the Shrikhande graph, displayed in Figure 1.21 (where vertices with the same label are to be identified), is strongly regular, with the same parameters as those of L(K4,4), but is not isomorphic to L(K4,4). 1.3.17 a) Show that: i) Aut(L(Kn)) ∼= Aut(Kn) for n = 2 and n = 4, ii) Aut(L(Kn)) ∼= Aut(Kn) for n = 3 and n ≥ 5. b) Appealing to Exercises 1.2.11 and 1.3.2, deduce that the automorphism group of the Petersen graph is isomorphic to the symmetric group S5
281 Graphs1020300010100Fig. 1.21. An embedding of the Shrikhande graph on the torus1.3.18 CAYLEY GRAPHLet T be a group, and let S be a set of elements of I not including the identityelement. Suppose, furthermore, that the inverse of every element of S also belongstoS.The Cayley graphofwithrespect toSisthegraph CG(,S) with vertexset r in whichverticesandyareadjacentif and onlyif ry-iES.(Notethat, because S is closed under taking inverses, if ry-1 e s, then yr-1 e s.)a) Show that the n-cube is a Cayley graphb) Let G be a Cayley graph CG(r,S) and let a be an element ofr.i) Show that the mapping Q defined by the rule that ar(y) = ry is anautomorphism of G.i) Deduce that every Cayley graph is vertex-transitive.c)Byconsidering the Petersen graph, show that not every vertex-transitive graphs a Cayley graph.1.3.19 CIRCULANTA circulant is a Cayley graphCG(Zn,S), where Z, is the additivegroupofintegersmodulo n. Let p be a prime, and let i and j be two nonzero elements of Zpa) Show that CG(Zp, (i, -il) = CG(Zp (j, -j),b) Determine when CG(Z, (1, -1,i, -ij) = CG(Zp, [1,-1,;j, -j).1.3.20 PALEY GRAPHLet q be a prime power, q= 1 (mod 4). The Paley graph PGg is the graph whosevertex set is the set of elements ofthefield GF(),two vertices being adjacentiftheir differenI nonzero square in GF(a)a) Draw PGs, PGg, and PG13b) Show that these three graphs are self-complementary.c) Let abe a nonsquare in GF(Q).By considering the mapping :GF(@)GF(α) defined by d(r) := ar, show that PGg is self-complementary for all q
28 1 Graphs 00 00 00 00 01 01 02 02 03 03 10 10 20 20 30 30 Fig. 1.21. An embedding of the Shrikhande graph on the torus 1.3.18 Cayley Graph Let Γ be a group, and let S be a set of elements of Γ not including the identity element. Suppose, furthermore, that the inverse of every element of S also belongs to S. The Cayley graph of Γ with respect to S is the graph CG(Γ,S) with vertex set Γ in which two vertices x and y are adjacent if and only if xy−1 ∈ S. (Note that, because S is closed under taking inverses, if xy−1 ∈ S, then yx−1 ∈ S.) a) Show that the n-cube is a Cayley graph. b) Let G be a Cayley graph CG(Γ,S) and let x be an element of Γ. i) Show that the mapping αx defined by the rule that αx(y) := xy is an automorphism of G. ii) Deduce that every Cayley graph is vertex-transitive. c) By considering the Petersen graph, show that not every vertex-transitive graph is a Cayley graph. 1.3.19 Circulant A circulant is a Cayley graph CG(Zn,S), where Zn is the additive group of integers modulo n. Let p be a prime, and let i and j be two nonzero elements of Zp. a) Show that CG(Zp, {i, −i}) ∼= CG(Zp, {j, −j}). b) Determine when CG(Zp, {1, −1,i, −i}) ∼= CG(Zp, {1, −1,j, −j}). 1.3.20 Paley Graph Let q be a prime power, q ≡ 1 (mod 4). The Paley graph PGq is the graph whose vertex set is the set of elements of the field GF(q), two vertices being adjacent if their difference is a nonzero square in GF(q). a) Draw PG5, PG9, and PG13. b) Show that these three graphs are self-complementary. c) Let a be a nonsquare in GF(q). By considering the mapping θ : GF(q) → GF(q) defined by θ(x) := ax, show that PGq is self-complementary for all q