Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / A / 3 / c / Solution

For $s,t\ge 2$, split $(s-1)(t-1)$ vertices into $s-1$ classes of size $t-1$, coloring edges between classes red and edges inside classes blue. The red graph has no $K_s$, and every blue component is too small for the connected tree. This proves the lower bound.

For the upper bound let $N=(s-1)(t-1)+1$ and suppose the blue graph contains no copy of the tree. By the permitted chromatic-number statement, its chromatic number is at most $t-1$. A graph of larger chromatic number would have a subgraph of chromatic number exactly $t$, obtained by deleting vertices until that number is reached. A proper blue coloring with at most $t-1$ classes puts no blue edges within any class, so each class is a red clique. If there is no red $K_s$, each class has at most $s-1$ vertices, contradicting $N>(s-1)(t-1)$. ThereforeThe one-vertex boundary cases give one directly.