Minimum Triangle-Free Graphs

We prove that \(e(3,k+1,n) \geq 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 \leq 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.