Counting substructures I: Color critical graphs

Abstract

Let F be a graph which contains an edge whose deletion reduces its chromatic number. We prove tight bounds on the number of copies of F in a graph with a prescribed number of vertices and edges. Our results extend those of Simonovits [8], who proved that there is one copy of F, and of Rademacher, Erdos [1, 2] and Lovasz- Simonovits [4], who proved similar counting results when F is a complete graph. One of the simplest cases of our theorem is the following new result. There is an absolute positive constant c such that if n is sufficiently large and 1 <= q < cn, then every n vertex graph with [n(2)/4] + q edges contains at least [equation] copies of a five cycle. Similar statements hold for any odd cycle and the bounds are best possible.