We show that for every k greater than or equal to 1 and delta > 0 there exi
sts a constant c > 0 such that, with probability tending to 1 as n --> infi
nity, a graph chosen uniformly at random among all triangle-free graphs wit
h n vertices and M greater than or equal to cn(3/2) edges can be made bipar
tite by deleting [delta M] edges. As an immediate consequence of this fact
we infer that if M/n(3/2)-->infinity but M/n(2)-->0, then the probability t
hat a random graph G(n, M) contains no triangles decreases as 2(-(1+0(1))M)
. We also discuss possible generalizations of the above results. (C) 2000 J
ohn Wiley & Sons, Inc.