Extremal graph theory David Conlon Lecture 1 bipartite graph between them.This graph has no triangles and [n2/4]edges. As a warm-up,we will give a number of different proofs of this simple and fundamental theorem. Theorem 1(Mantel's theorem)If a graph G on n vertices contains no triangle then it contain at most edges. First proof Suppose that G has m edges.Let x and y be two vertices in G which are joined by an edge.If d(v)is the degree of a vertex v,we see that d(r)+d(y)<n.This is because every vertex in the graph G is connected to at most one of z and y.Note now that ∑dP(e)=∑(d(x)+dg)≤mn. On the other hand,since d()=2m,the Cauchy-Schwarz inequality implies that ∑r回≥区P≥ n Therefore 把≤m and the result follows. Second proof We proceed by induction on n.For n=1 and n=2,the result is trivial,so assume that we know it to be true for n-1 and let G be a graph on n vertices.Let z and y be two adjacent vertices in G.As above,we know that d(c)+d(y)sn.The complement H of r and y has n-2 vertices and since it contains no triangles must,by induction,have at most (n-2)2/4 edges.Therefore,the total number of edges in G is at most m+da+d0-1sa2+n-1-号 where the-1 comes from the fact that we count the edge between r and y twice.Extremal graph theory David Conlon Lecture 1 The basic statement of extremal graph theory is Mantel’s theorem, proved in 1907, which states that any graph on n vertices with no triangle contains at most n 2/4 edges. This is clearly best possible, as one may partition the set of n vertices into two sets of size bn/2c and dn/2e and form the complete bipartite graph between them. This graph has no triangles and bn 2/4c edges. As a warm-up, we will give a number of different proofs of this simple and fundamental theorem. Theorem 1 (Mantel’s theorem) If a graph G on n vertices contains no triangle then it contains at most n 2 4 edges. First proof Suppose that G has m edges. Let x and y be two vertices in G which are joined by an edge. If d(v) is the degree of a vertex v, we see that d(x) + d(y) ≤ n. This is because every vertex in the graph G is connected to at most one of x and y. Note now that X x d 2 (x) = X xy∈E (d(x) + d(y)) ≤ mn. On the other hand, since P x d(x) = 2m, the Cauchy-Schwarz inequality implies that X x d 2 (x) ≥ ( P x d(x))2 n ≥ 4m2 n . Therefore 4m2 n ≤ mn, and the result follows. ✷ Second proof We proceed by induction on n. For n = 1 and n = 2, the result is trivial, so assume that we know it to be true for n − 1 and let G be a graph on n vertices. Let x and y be two adjacent vertices in G. As above, we know that d(x)+d(y) ≤ n. The complement H of x and y has n−2 vertices and since it contains no triangles must, by induction, have at most (n − 2)2/4 edges. Therefore, the total number of edges in G is at most e(H) + d(x) + d(y) − 1 ≤ (n − 2)2 4 + n − 1 = n 2 4 , where the −1 comes from the fact that we count the edge between x and y twice. ✷ 1