A note on sparse random graphs and cover graphs (Q1972677)

Summary: It is shown in this note that with high probability it is enough to destroy all triangles in order to get a cover graph from a random graph \(G_{n,p}\) with \(p\leq \kappa\log n/n\) for any constant \(\kappa<2/3\). On the other hand, this is not true for somewhat higher densities: If \(p\geq \lambda (\log n)^3 / (n\log\log n)\) with \(\lambda > 1/8\) then with high probability we need to delete more edges than one from every triangle. Our result has a natural algorithmic interpretation.