Large induced trees in -free graphs

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 Erdős, Saks, and Sós. Substantially improving earlier results of various researchers, we prove that every connected triangle-free graph on n vertices contains an induced tree of order 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 Matoušek and Šámal.