1. The problem statement, all variables and given/known data Homework, from Modern Graph Theory by Bela Bollobas, section on extremals: 1. Suppose that G is a graph with n > r + 1 vertices and tr(n) + 1 edges. (a) Prove that for every p with r + 1 < p <= n there is a subgraph H of G with |H| = p and e(H) >= tr(p) + 1. [Hint: Try to copy the proof of Turan’s Theorem. You may wish to write n = qr + x where 0 <= x < r, and consider the cases x = 0, x = 1 and x > 2.] (b) Prove that G contains two copies of Kr+1 with exactly r common vertices 2. Relevant equations tr(n) − δ(Tr(n)) = tr(n − 1). where tr(n) is the Turan number, Tr(n) the Turan graph, and δ(G) is the minimum degree of G 3. The attempt at a solution Use a descending induction on p. Assume there exists a subgraph of order p and size greater or equal to tr(p) + 1. Identify a vertex v with deg(v) <= δ(Tr(p)) = p - roof(p/r) Delete v and its incident vertices Since tr(p) − δ(Tr(p)) = tr(p − 1) the result is a subgraph of order p-1 and size greater or equal to tr(p-1) + 1 as required. The result follows by induction. The crucial step is proving the existence of a suitable v, which I've no clue how to do.