Independence, odd girth, and average degree

We prove several tight lower bounds in terms of the order and the average degree for the independence number of graphs that are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle‐free graphs of maximum degree at most three due to Heckman and Thomas [Discrete Math 233 (2001), 233–237] to arbitrary triangle‐free graphs. For connected triangle‐free graphs of order n and size m , our result implies the existence of an independent set of order at least (4 n − m −1)/7. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:96‐111, 2011