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

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

Solved by gpt-5.6-sol high.