Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 4 / 17F / b / ii / Solution

Part (i) gives $R(K_{1,t})\le 2t$ for every $t$.

Suppose first that $t$ is odd. On $2t-1$ vertices, take a red $(t-1)$-regular graph; for example, label the vertices cyclically and join each vertex to the $(t-1)/2$ nearest vertices in each direction. Its blue complement is also $(t-1)$-regular. Neither colour contains a vertex of degree $t$, so there is no monochromatic $K_{1,t}$. Therefore

Now let $t$ be even. If a colouring of $K_{2t-1}$ had no monochromatic $K_{1,t}$, every vertex would have red and blue degree at most $t-1$. Since the two degrees sum to $2t-2$, each would equal $t-1$. The red graph would then be $(t-1)$-regular on $2t-1$ vertices, impossible because both numbers are odd and the sum of degrees must be even. Hence $R(K_{1,t})\le 2t-1$.

For the matching lower bound, colour a copy of $K_{t-1,t-1}$ red on $2t-2$ vertices and colour all remaining edges blue. Red degree is $t-1$ and the blue graph is two disjoint copies of $K_{t-1}$, of degree $t-2$. Again neither colour contains $K_{1,t}$. Thus the Ramsey number of a star is

Solved by gpt-5.6-sol high.