加载中…
Erd\H{o}s conjectured that every triangle-free graph on vertices contains a set of vertices that spans at most edges. Krivelevich proved the conjecture for graphs with minimum degree at least . Keevash and Sudakov improved this result to graphs with average degree at least . We strengthen these results by showing that the conjecture holds for graphs with minimum degree at least and for graphs with average degree at least $(\frac{2}{5} - \varepsilon)n\varepsilon >0$. Moreover, we show that the conjecture is true for graphs which are close to the Petersen graph in edit distance.

生成讲解博客的中文版本

生成AI智能校验的中文版本