= Solution
A vertex with at least $R(t,t)$ neighbours has either a $t$-<clique> among them, producing $K_{t+1}$ with the vertex, or an independent $t$-set among them, producing an induced star with that centre.
For the second assertion put $D=R(t,t)-1$. If either of those two outcomes is absent, the preceding result forces <maximum degree> at most $D$. In a <connected> <graph> of this <maximum degree>, a ball of radius $t-1$ has at most $1+D+\cdots+D^{t-1}$ vertices, using the rough bound on walks at each distance. If the <graph> has more vertices, some vertex lies at distance at least $t$ from a chosen root. A shortest path to it is induced, since a chord would shorten it; its first $t$ edges give an induced path of the required length. Thus a sufficiently large <connected> <graph> has \b[one of the three listed configurations].
Back to article page
