Minimum Triangle-Free Graphs

Abstract

We prove that $e(3,k+1,n)\ge 6n-13k$, where $e(3,k+1,n)$ is the minimum number of edges in any triangle-free graph on $n$ vertices with no independent set of size $k+1$. To achieve this, we first characterize all such graphs with exactly $e(3,k+1,n)$ edges for $n\le 3k$. These results yield some sharp lower bounds for the independence ratio for triangle-free graphs. In particular, the exact value of the minimal independence ratio for graphs with average degree $4$ is shown to be $\frac{4}{13}$. A slight improvement to the general upper bound for the classical Ramsey $R(3,k)$ numbers is also obtained.