  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.
