\magnification=1200
\hsize=4in
\nopagenumbers
\noindent
 {\bf  Tom Bohman, Alan Frieze,  Mikl\'os Ruszink\'o and Lubos Thoma }
\medskip
\noindent {\bf A Note on Sparse Random Graphs and Cover Graphs }

 \vskip.5cm

\noindent 
 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\le \kappa \log n/n$ for any constant $\kappa <2/3$. On the other hand, this
is not true for
somewhat higher densities: If
$p\ge \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.
\bye






.