= Solution
For $s,t\ge2$, 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)$. Therefore
$$
\boxed{R(K_s,T)=(s-1)(t-1)+1}.
$$
The one-vertex boundary cases give one directly.
Back to article page
