Extremal graph theory David Conlon
Extremal graph theory David Conlon
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
Third proof let a be the largest independent set in the graph G.since the neighborhood of everv vertexisan independent we must have d()A.Let B be the complement of A.Every edge in G must meet a vertex of B.Therefore,the number of edges in G satisfies 4a≤Σs≤（生）- Suppose that n is even.Then equality holds if and only if A =B=n/2,d(z)=|Al for every B and B has no internal edges.This easily implies that the unique structure with n2/4 edges is a bipartite graph with equal partite sets.For n odd,the number of edges is maximised when A [n/2] and B=n/2].Again,this yields a unique bipartite structure. ▣ The last proof tells us that not only is [n2/4]the maximum number of edges in a triangle-free graph but also that any triangle-free graph with this number of edges is bipartite with partite sets of almost equal size. The natural generalisation of this theorem to cliques of size r is the following,proved by Paul Turan in1941. Theorem 2 (Turan's theorem)If a graph G on n vertices contains no copy of Kr+,the complete graph onr+1 vertices,then it contains at most (1-1)edges. First proof By induction on n.The theorem is trivially true for n=1,2....,.We will therefore assume that it is true for all values less than n and prove it for n.Let G be a graph on n vertices which contains no K+and has the maximum possible number of edges.Then G contains copies of K.Otherwise,we could add edges to G,contradicting maximality. Let A be a clique of size r and let B be its complement.Since B has size n-r and contains no Kr+ there are at most (1-1)edges in B.Moreover,since every vertex in B can have at most r-1 neighbours in A,the number of edges between A and B is at most (r-1)(n-r).Summing,we see that e4@=ea+caa+B≤（付）+G-10a-m+(-)a,=(-) 21 where eA,eA.B and eg are the number of edges in A,between A and B and in B respectively.The theorem follows. ■ Second proof We again assume that has the maximum possible number of edges.We will begin by proving that if ry E(G)and yz E(G),then rzE(G).This implies that the property of not being connected in G is an equivalence relation.This in turn will imply that the graph must be a complete multipartite graph. Suppose,for contradiction,that ry E(G)and yz(G),but xz E(G).If d(y)<d(a)then we m a new Kr+1-free graph G'by deleting y and creating a new copy of the vertex say Since a eioue in can contain at most one of andwe sce thatse Moreover. E(G)=E(G)I-d(y)+d()>E(G), contradicting the maximality of G.A similar conclusion holds if d(y)<d(z).We may therefore assume that d(y)>d(x)and d(y)>d(z).We create a new graph G"by deleting x and z and creating two extra copies of the vertex y.Again,this has no Kr+and 1E(G")1=1E(G-(dx)+d(z)-1)+2d(y)>1E(G 2
Third proof Let A be the largest independent set in the graph G. Since the neighborhood of every vertex x is an independent set, we must have d(x) ≤ |A|. Let B be the complement of A. Every edge in G must meet a vertex of B. Therefore, the number of edges in G satisfies e(G) ≤ X x∈B d(x) ≤ |A||B| ≤ |A| + |B| 2 2 = n 2 4 . Suppose that n is even. Then equality holds if and only if |A| = |B| = n/2, d(x) = |A| for every x ∈ B and B has no internal edges. This easily implies that the unique structure with n 2/4 edges is a bipartite graph with equal partite sets. For n odd, the number of edges is maximised when |A| = dn/2e and |B| = bn/2c. Again, this yields a unique bipartite structure. ✷ The last proof tells us that not only is bn 2/4c the maximum number of edges in a triangle-free graph but also that any triangle-free graph with this number of edges is bipartite with partite sets of almost equal size. The natural generalisation of this theorem to cliques of size r is the following, proved by Paul Tur´an in 1941. Theorem 2 (Tur´an’s theorem) If a graph G on n vertices contains no copy of Kr+1, the complete graph on r + 1 vertices, then it contains at most 1 − 1 r n 2 2 edges. First proof By induction on n. The theorem is trivially true for n = 1, 2, . . . , r. We will therefore assume that it is true for all values less than n and prove it for n. Let G be a graph on n vertices which contains no Kr+1 and has the maximum possible number of edges. Then G contains copies of Kr. Otherwise, we could add edges to G, contradicting maximality. Let A be a clique of size r and let B be its complement. Since B has size n − r and contains no Kr+1, there are at most 1 − 1 r (n−r) 2 2 edges in B. Moreover, since every vertex in B can have at most r − 1 neighbours in A, the number of edges between A and B is at most (r − 1)(n − r). Summing, we see that e(G) = eA + eA,B + eB ≤ r 2 + (r − 1)(n − r) + 1 − 1 r (n − r) 2 2 = 1 − 1 r n 2 2 , where eA, eA,B and eB are the number of edges in A, between A and B and in B respectively. The theorem follows. ✷ Second proof We again assume that G contains no Kr+1 and has the maximum possible number of edges. We will begin by proving that if xy /∈ E(G) and yz /∈ E(G), then xz /∈ E(G). This implies that the property of not being connected in G is an equivalence relation. This in turn will imply that the graph must be a complete multipartite graph. Suppose, for contradiction, that xy /∈ E(G) and yz /∈ E(G), but xz ∈ E(G). If d(y) < d(x) then we may construct a new Kr+1-free graph G0 by deleting y and creating a new copy of the vertex x, say x 0 . Since any clique in G0 can contain at most one of x and x 0 , we see that G0 is Kr+1-free. Moreover, |E(G 0 )| = |E(G)| − d(y) + d(x) > |E(G)|, contradicting the maximality of G. A similar conclusion holds if d(y) < d(z). We may therefore assume that d(y) ≥ d(x) and d(y) ≥ d(z). We create a new graph G00 by deleting x and z and creating two extra copies of the vertex y. Again, this has no Kr+1 and |E(G 00)| = |E(G)| − (d(x) + d(z) − 1) + 2d(y) > |E(G)|, 2
so again we have a contradiction. We now know that the graph is a complete multipartite graph.Clearly,it can have at mostparts We will show that the number of edges is maximised when all of these parts have sizes which differ by at most one.Indeed,if there were two parts A and B with A>B+1,we could increase the number of edges in G by moving one vertex from A to B.We would lose Bl edges by doing this,but gain A]-1.Overall,we would gain A]-1-|B]2 1. ◇ This second proof also determines the structure of the extremal graph,that is,it must be r-partite with all parts having size as close as possible.So if n=mr+,we get g sets of size m+1 and r-q sets of size m. 3
so again we have a contradiction. We now know that the graph is a complete multipartite graph. Clearly, it can have at most r parts. We will show that the number of edges is maximised when all of these parts have sizes which differ by at most one. Indeed, if there were two parts A and B with |A| > |B| + 1, we could increase the number of edges in G by moving one vertex from A to B. We would lose |B| edges by doing this, but gain |A| − 1. Overall, we would gain |A| − 1 − |B| ≥ 1. ✷ This second proof also determines the structure of the extremal graph, that is, it must be r-partite with all parts having size as close as possible. So if n = mr + q, we get q sets of size m + 1 and r − q sets of size m. 3
Lecture 2 A perfect matching in a bipartite graph with two sets of equal size is a collection of edges such that every vertex is contained in exactly one of them. Hall's(marriage)theorem is a necessary and sufficient condition which allows one to decide if a given bipartite graph contains a matching.Suppose that the two parts of the bipartite graph G are A and B.Then Hall's theorem says that if,for every subset U of A,there are at least vertices in B with neighbours in U then G contains a perfect matching The condition is clearly necessary.To prove that it is sufficient we use the following notation. For any subset X of a graph G,let NG(X)be the set of neighbours of X,that is,the set of vertices with a neighbour in X. Theorem 1 (Hall's theorem)Let G be a bipartite graph with parts A and B of equal size.If,for every U C A,NG(U)>U then G contains a perfect matching. Proof Let Al =BI=n.We will prove the theorem by induction on n.Clearly,the result is true for n=1.We therefore assume that it is true for n-1 and prove it for n. If N(U)1 for every non-empty proper sabset U of A,pick an edge ofGand consider the e graph G=G-{a,b).Then every non-empty set U C}satisfies INc(U)I≥lNc(U)I-1≥IUL. Therefore,there is a perfect matching between}and B\).Adding the edge from a to b gives the full matching. proper subset Uof A for which NU) eN.y indnetion since Hail's condition holds for evry subset of V.there sa inatching re is some nor empty p between U and V.But Hall's condition also holds between A\U and B\V.If this weren't the case, there would be some W in AlU with fewer than WI neighbours in B\V.Then WUU would be n B,contradicting our assumption. Therefore. thrhn t and BV.Putting the to tch o the proof. ■ A Hamiltonian cycle in a graph G is a cycle which visits every vertex exactly once and returns to its starting vertex.Dirac's theorem says that if the minimum degree 6(G)of a graph G is such that 6(G)2n/2 then G contains a Hamiltonian cycle.This is sharp since,if one takes a complete bipartite graph with one part of size(and the other the complement of this),then it canot contain a Hamiltonian cycle.This is simply because one must pass back and forth between the two sets. Theorem 2(Dirac's theorem)If a graph G satisfies 6(G)>,then it contains a Hamiltonian cycle Proof First,note that G is connected.If it weren't,the smallest component would have size at most n/2 and no vertex in this component could have degree n/2 or more. Let P=zoz1...k be a longest path in G.Since it can't be extended,every neighbour of ro and rk must be contained in P.Since (G)2n/2,we see that roi+is an edge for at least n/2 values of i 1
Lecture 2 A perfect matching in a bipartite graph with two sets of equal size is a collection of edges such that every vertex is contained in exactly one of them. Hall’s (marriage) theorem is a necessary and sufficient condition which allows one to decide if a given bipartite graph contains a matching. Suppose that the two parts of the bipartite graph G are A and B. Then Hall’s theorem says that if, for every subset U of A, there are at least |U| vertices in B with neighbours in U then G contains a perfect matching. The condition is clearly necessary. To prove that it is sufficient we use the following notation. For any subset X of a graph G, let NG(X) be the set of neighbours of X, that is, the set of vertices with a neighbour in X. Theorem 1 (Hall’s theorem) Let G be a bipartite graph with parts A and B of equal size. If, for every U ⊂ A, |NG(U)| ≥ |U| then G contains a perfect matching. Proof Let |A| = |B| = n. We will prove the theorem by induction on n. Clearly, the result is true for n = 1. We therefore assume that it is true for n − 1 and prove it for n. If |NG(U)| ≥ |U| + 1 for every non-empty proper subset U of A, pick an edge {a, b} of G and consider the graph G0 = G − {a, b}. Then every non-empty set U ⊂ A\{a} satisfies |NG0(U)| ≥ |NG(U)| − 1 ≥ |U|. Therefore, there is a perfect matching between A\{a} and B\{b}. Adding the edge from a to b gives the full matching. Suppose, on the other hand, that there is some non-empty proper subset U of A for which |N(U)| = |U|. Let V = N(U). By induction, since Hall’s condition holds for every subset of U, there is a matching between U and V . But Hall’s condition also holds between A\U and B\V . If this weren’t the case, there would be some W in A\U with fewer than |W| neighbours in B\V . Then W ∪ U would be a subset of A with fewer than |W ∪ U| neighbours in B, contradicting our assumption. Therefore, there is a perfect matching between A\U and B\V . Putting the two matchings together completes the proof. ✷ A Hamiltonian cycle in a graph G is a cycle which visits every vertex exactly once and returns to its starting vertex. Dirac’s theorem says that if the minimum degree δ(G) of a graph G is such that δ(G) ≥ n/2 then G contains a Hamiltonian cycle. This is sharp since, if one takes a complete bipartite graph with one part of size d n 2 − 1e (and the other the complement of this), then it cannot contain a Hamiltonian cycle. This is simply because one must pass back and forth between the two sets. Theorem 2 (Dirac’s theorem) If a graph G satisfies δ(G) ≥ n 2 , then it contains a Hamiltonian cycle. Proof First, note that G is connected. If it weren’t, the smallest component would have size at most n/2 and no vertex in this component could have degree n/2 or more. Let P = x0x1 . . . xk be a longest path in G. Since it can’t be extended, every neighbour of x0 and xk must be contained in P. Since δ(G) ≥ n/2, we see that x0xi+1 is an edge for at least n/2 values of i 1