G that induces a tree. We investigate the relationship of t(G)to other parameters associated with G : the number of vertices and edges, the radius, the independence number, maximum clique size and connectivity . The central result is a set of upper and lower bounds for the function f(n, p), defined to be the minimum ofover all connected graphs with n vertices andn-1 +p edges. The bounds obtained yield an asymptotic characterization of the function correct to leading order in almost all ranges. The results show that f(n, p)is surprisingly small ; in particular ,fin, (n)=2loglogn+OfogloglogP) for any constant c>0, and fin,ti"T ) = 2log(I + 1 ~) ,)± 4 for 0< 1 and n sufficiently large . Bounds ont(G)are obtained in terms of the size of the largest clique . These are used to formulate bounds for a Ramsey-type function, N(k, t), the smallest integer so that every connected graph on N(k, t) vertices has either a clique of size k or an induced tree of size t.Tight bounds fort(G)from the independence number a(G)are also proved . It is shown that every connected graph with radius r has an induced path, and hence an induced tree, on 2r- I vertices .
['Paul Erdös', 'Michael E. Saks', 'Vera T. Sós']
Maximum induced trees in graphs