Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-4/17f/b/iii/solution
Past exam of the mathematics course of the University of Cambridge 2025 ii Paper 4 17F b iii Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
For the lower bound, partition the vertices of 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 , so there is no monochromatic copy of . Hence .
For the upper bound, every colouring of contains a monochromatic triangle because . Suppose that a triangle is red, and let be the other four vertices. If any edge from to were red, it would be a pendant edge extending to a red . Thus all edges between and are blue.
If an edge inside were blue, then for any the vertices would form a blue triangle, and an edge from a second vertex of to would extend it to a blue . Therefore every edge inside is red. The resulting red contains a red triangle and an additional incident edge, hence a red . The blue-triangle case is symmetric, so the Ramsey number of the paw graph is
New to topics? Read the docs here!