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