  For a graph G, let t(G) denote the maximum number of vertices in an induced
subgraph of G that is a tree. In this paper, we study the problem of bounding
t(G) for graphs which do not contain a complete graph K_r on r vertices. This
problem was posed twenty years ago by Erdos, Saks, and Sos. Substantially
improving earlier results of various researchers, we prove that every connected
triangle-free graph on n vertices contains an induced tree of order \sqrt{n}.
When r >= 4, we also show that t(G) >= (\log n)/(4 \log r) for every connected
K_r-free graph G of order n. Both of these bounds are tight up to small
multiplicative constants, and the first one disproves a recent conjecture of
Matousek and Samal.
