Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 3 / 17F (Graph Theory)

Define the asymmetric Ramsey number $R(s,t)$ for a red $K_s$ or a blue $K_t$. The base cases $R(1,t)=R(s,1)=1$ are finite. If $n=R(s-1,t)+R(s,t-1)$, choose a vertex of $K_n$. Its red neighbors number at least $R(s-1,t)$, or its blue neighbors number at least $R(s,t-1)$. Apply the appropriate smaller Ramsey number inside that neighborhood: either the opposite-color clique already exists, or a same-color clique extends by the chosen vertex. Thus $R(s,t)\le R(s-1,t)+R(s,t-1)$, proving finiteness by induction, in particular for $R(s)=R(s,s)$.

In a graph of maximum degree $d\ge 2$, a ball of radius $k-1$ about a vertex has at most ${\sum }_{j=0}^{k-1}{d}^j=(d^k-1)/(d-1)<d^k$ vertices. Hence a connected graph of order $d^k$ has a vertex outside this ball, at distance at least $k$. The argument also applies whenever the graph has at least $d^k$ vertices.

Now take a connected graph of order $R(s{)}^s$. If some vertex has at least $R(s)$ neighbors, apply the two-color Ramsey theorem to their pairs, coloring an edge red and a nonedge blue. A red $K_s$ is an induced complete graph, while a blue $K_s$ is an independent set of $s$ neighbors, which with the centre induces $K_{1,s}$. Otherwise the maximum degree satisfies $d<R(s)$. For $s\ge 2$, connectedness and the vertex count rule out $d\le 1$. The ball bound then provides vertices at distance at least $s$. A shortest path between them has no chord, since a chord would shorten it; its first $s$ edges induce $P_s$. The case $s=1$ is immediate. Therefore