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