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

The graph Ramsey number $R(G)$ is the least positive integer $n$ for which every red-blue colouring of $K_n$ contains a monochromatic copy of $G$. If $g=|V(G)|$, the Ramsey theorem gives a monochromatic $K_g$ in every colouring of $K_{R(g)}$, and that clique contains $G$. Hence

Choose any vertex $v$ of $K_{2t}$. Its $2t-1$ incident edges have two colours, so at leasthave the same colour. Those edges, together with $v$, form a monochromatic $K_{1,t}$.

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

Here $H$ is the paw graph, a triangle with a pendant edge.

For the lower bound, partition the vertices of $K_6$ into two triples. Colour the edges inside each triple red and all edges between the triples blue. Each red component is only a triangle, while the blue graph is the triangle-free graph $K_{3,3}$, so there is no monochromatic copy of $H$. Hence $R(H)>6$.

For the upper bound, every colouring of $K_7$ contains a monochromatic triangle because $R(3)=6$. Suppose that a triangle $T$ is red, and let $S$ be the other four vertices. If any edge from $T$ to $S$ were red, it would be a pendant edge extending $T$ to a red $H$. Thus all edges between $T$ and $S$ are blue.

If an edge $xy$ inside $S$ were blue, then for any $u\in T$ the vertices $u,x,y$ would form a blue triangle, and an edge from a second vertex of $T$ to $x$ would extend it to a blue $H$. Therefore every edge inside $S$ is red. The resulting red $K_4$ contains a red triangle and an additional incident edge, hence a red $H$. The blue-triangle case is symmetric, so the Ramsey number of the paw graph is