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), 233237] 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 (4n?m?1)/7.  2010 Wiley Periodicals, Inc. J Graph Theory 67:96-111, 2011
independence odd girth triangle-free graph stability