Abstract :
Turánʹs theorem (Mat. Fiz. Lapok 48 (1941) 436) (or rather its extension by Zykov (Mat. Sbornik 24 (66) (1949) 163) answers the following question: For k=2,…,r, what is the maximum number of k-cliques (i.e., subgraphs on k vertices) in a finite graph G, given the clique number r and the number of vertices of G? Here we address—and answer—the following closely related question: For k=3,…,r, what is the maximum number of k-cliques in G, given the clique number r and the number of edges of G? We also prove a “stability theorem” which shows that our result is best possible in a strong sense.
