Graphs with unavoidable subgraphs with large degrees

Let ( n, m ) denote the class of simple graphs on n vertices and m edges and let G ∈ ( n, m ). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a K k + 1 in terms of the number of edges in G . In this paper we prove that, for m = α n 2 , α > ( k ‐ 1)/2 k , G contains a K k + 1 , each vertex of which has degree at least f (α) n and determine the best possible f (α). For m = ⌊ n 2 /4⌋ + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = α n 2 , α > 0 we establish that G contains a subgraph H with δ( H ) ≥ f (α, n ) and determine the best possible value of f (α, n ).