Let c(t) be the minimum number c such that every graph G with c(G)greater t
han or equal toc \G \ contracts to a complete graph K-p. We show that
c(t) = (alpha + o(1))t log t
where x=0.319... is an explicit constant. Random graphs are extremal graphs
. (C) 2001 Academic Press.