26210 Planar Graphsc)ExpresstheTuran graph Te 13 (defined in Exercise1.1.11)as the union of twegraphs,eachisomorphictotheicosahedrond) Deduce from (b) and (c) that (K12) = 3.10.3.7a) Let G be a simple bipartite graph. Show that e(G) ≥ [m/(2n - 4)].b) Deduce that 0(Km.n) ≥[mn/(2m + 2n - 4)l.(Beineke et al. (1964) showed that equality holds if mn is even. It is conjecturedthat equality holds in all cases.)10.3.8 A plane graph is self-dual if it is isomorphic to its duala)Show thai) if G is self-dual, then e(G) = 2v(G) - 2ii) the four plane graphs shown in Figure 10.14 are self-dual.b) Find four infinite families of self-dual plane graphs of which those four graphsaremembers(Smith and Tutte (1950) proved that every self-dual plane graph belongs to oneoffour infinitefamilies.)人A区MFig. 10.14. Self-dual plane graphs10.3.9a) Let S befofrts intheplane.wheren >3 and thedistaany two points of S is at least one. Show that no more than 3n - 6 pairs ofpoints of S can be at distance exactly one(P.ERDOS)b)By considering the triangularlaice (shown in Figure 1.27) find, for eachpositive integer k, a set S of 3k? + 3k + 1 points in the plane such that thedistance between any two points of S is at least one, and such that 9k2 + 3kpairs of points of S are at distance exactly one10.3.10 THE SYLVESTER-GALLAI THEOREMa) Let C be a finite set of lines in the plane, no two of which are parallel andnotall ofwhichare concurrent.UsingEuler'sFormula(10.2),showthatsomepoint is the point of intersection of precisely two lines of C.b) Deduce from (a) the Syluester-Gallai Theorem: if S is a finite set of points inthe plane, not all of which are collinear, there is a line that contains precisely(E. MELCHIOR)two points of S.262 10 Planar Graphs c) Express the Tur´an graph T6,12 (defined in Exercise 1.1.11) as the union of two graphs, each isomorphic to the icosahedron. d) Deduce from (b) and (c) that θ(K12) = 3. 10.3.7 a) Let G be a simple bipartite graph. Show that θ(G) ≥ m/(2n − 4) . b) Deduce that θ(Km,n) ≥ mn/(2m + 2n − 4) . (Beineke et al. (1964) showed that equality holds if mn is even. It is conjectured that equality holds in all cases.) 10.3.8 A plane graph is self-dual if it is isomorphic to its dual. a) Show that: i) if G is self-dual, then e(G)=2v(G) − 2, ii) the four plane graphs shown in Figure 10.14 are self-dual. b) Find four infinite families of self-dual plane graphs of which those four graphs are members. (Smith and Tutte (1950) proved that every self-dual plane graph belongs to one of four infinite families.) Fig. 10.14. Self-dual plane graphs 10.3.9 a) Let S be a set of n points in the plane, where n ≥ 3 and the distance between any two points of S is at least one. Show that no more than 3n − 6 pairs of points of S can be at distance exactly one. (P. Erdos) ˝ b) By considering the triangular lattice (shown in Figure 1.27) find, for each positive integer k, a set S of 3k2 + 3k + 1 points in the plane such that the distance between any two points of S is at least one, and such that 9k2 + 3k pairs of points of S are at distance exactly one. 10.3.10 The Sylvester–Gallai Theorem a) Let L be a finite set of lines in the plane, no two of which are parallel and not all of which are concurrent. Using Euler’s Formula (10.2), show that some point is the point of intersection of precisely two lines of L. b) Deduce from (a) the Sylvester–Gallai Theorem: if S is a finite set of points in the plane, not all of which are collinear, there is a line that contains precisely two points of S. (E. Melchior)