Counting substructures I: Color critical graphs

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 (1968) [8], who proved that there is one copy of F, and of Rademacher, Erdos (1962) [1,2] and Lovasz and Simonovits (1983) [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 left perpendicularn/2right perpendicular(left perpendicularn/2right perpendicular - 1)(inverted right perpendicularn/2inverted left perpendicular - 2) copies of a five cycle. Similar statements hold for any odd cycle and the bounds are best possible. (C) 2010 Elsevier Inc. All rights reserved.