A conjecture of Chung and Graham states that every $K_4$-free graph on $n$ vertices contains a vertex set of size $lfloor n/2 rfloor$ that spans at most $n^2/18$ edges. We make the first step toward this conjecture by showing that it holds for all regular graphs.
تحميل البحث