A new Turán-type theorem for cliques in graphs Original Research Article

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.