with 0ik-1.Similarly,itk is an edge for at least n/2 values of i.There are at most n- values of i with 0si<k-1.Therefore,since the total number of edges of the form roxi+or of the form rizk with 0<ik-1 is at least n,there must be some i for which both rozi+1 and ritk are edges in G. We claim that C=x02+1r+2…xk工i2i-120 is a Hamiltonian cycle.Suppose not and that there is a set of vertices Y which are not contained in C.Then,since G is connected,there is a vertex z;and a vertex y in Y such that ziy is in E(G).But then we may define a path Pstarting at goingtoand then around the cycle which is longer than P.This would contradict our assumption about P. A tree T is a connected graph containing no cycles.The Erdos-Sos conjecture states that if a tree T has t edges,then any graph G with average degree t must contain a copy of T.This conjecture has been proven,for sufficiently large graphs G,by Ajtai,Komlos,Simonovits and Szemeredi.Here we prove a weaker version of this conjecture. Theorem 3 If a graph G has average degree 2t,it contains every tree T with t edges. Proof We start with a standard reduction,by showing that a graph of average degree 2t has a subgraph of minimum degree t.If the number of vertices in G is n,the number of edges in G is at least tn.If there is a vertex of degree less than t,delete it.This will not decrease the average degree. Moreover,the process must end,since any graph with fewer than 2 vertices cannot have average degree 2t We now use this condition to embed the vertices of the tree greedily.Suppose we have already embedded j vertices,where j<t+1.We will try to embed a new vertex which is connected to some already embedded vertex.By the minimum degree condition,there are at least t possible places to embed this vertex.At most t-1of these are blocked by already embedded vertices,so the embedding may always proceed. 2with 0 ≤ i ≤ k − 1. Similarly, xixk is an edge for at least n/2 values of i. There are at most n − 1 values of i with 0 ≤ i ≤ k − 1. Therefore, since the total number of edges of the form x0xi+1 or of the form xixk with 0 ≤ i ≤ k − 1 is at least n, there must be some i for which both x0xi+1 and xixk are edges in G. We claim that C = x0xi+1xi+2 . . . xkxixi−1 . . . x0 is a Hamiltonian cycle. Suppose not and that there is a set of vertices Y which are not contained in C. Then, since G is connected, there is a vertex xj and a vertex y in Y such that xjy is in E(G). But then we may define a path P 0 starting at y, going to xj and then around the cycle C which is longer than P. This would contradict our assumption about P. ✷ A tree T is a connected graph containing no cycles. The Erd˝os-S´os conjecture states that if a tree T has t edges, then any graph G with average degree t must contain a copy of T. This conjecture has been proven, for sufficiently large graphs G, by Ajtai, Koml´os, Simonovits and Szemer´edi. Here we prove a weaker version of this conjecture. Theorem 3 If a graph G has average degree 2t, it contains every tree T with t edges. Proof We start with a standard reduction, by showing that a graph of average degree 2t has a subgraph of minimum degree t. If the number of vertices in G is n, the number of edges in G is at least tn. If there is a vertex of degree less than t, delete it. This will not decrease the average degree. Moreover, the process must end, since any graph with fewer than 2t vertices cannot have average degree 2t. We now use this condition to embed the vertices of the tree greedily. Suppose we have already embedded j vertices, where j < t + 1. We will try to embed a new vertex which is connected to some already embedded vertex. By the minimum degree condition, there are at least t possible places to embed this vertex. At most t−1 of these are blocked by already embedded vertices, so the embedding may always proceed. ✷ 2