Compactness results in extremal graph theory

Let L be a given family of so called prohibited graphs. Let ex (n, L) denote the maximum number of edges a simple graph of ordern can have without containing subgraphs from L. A typical extremal graph problem is to determine ex (n, L), or at least, find good bounds on it. Results asserting that for a given L there exists a much smaller L*⫅L for which ex (n, L) ≈ ex (n, L*) will be calledcompactness results. The main purpose of this paper is to prove some compactness results for the case when L consists of cycles. One of our main tools will be finding lower bounds on the number of pathsP ^k+1 in a graph ofn vertices andE edges., witch is, in fact, a “super-saturated” version of a wellknown theorem of Erdős and Gallai. Dedicated to Tibor Gallai on his seventieth birthday