THE LARGEST INDUCED TREE IN A SPARSE RANDOM GRAPH

The author proved that, for c > 1, the random graph G(n, p) on n verti ces with edge probability p = c/n contains almost always an induced tr ee on at least alpha(c)n(1 - o(1)) vertices, where alpha(c) is the pos itive root of the equation c alpha = log(1 + c(2) alpha). It is shown here that if c is sufficiently large, then the largest size of an indu ced tree in G(n, p), p = c/n, is almost always at least 2n/c(log c - l og log c - 1). The proof relies heavily on a theorem of Frieze concern ing the independence number of a sparse random graph. (C) 1996 John Wi ley & Sons, Inc.