Paper 4, Section II, I

Graph Theory | Part II, 2018

Let s3s \geqslant 3. Define the Ramsey number R(s)R(s). Show that R(s)R(s) exists and that R(s)4sR(s) \leqslant 4^{s}.

Show that R(3)=6R(3)=6. Show that (up to relabelling the vertices) there is a unique way to colour the edges of the complete graph K5K_{5} blue and yellow with no monochromatic triangle.

What is the least positive integer nn such that the edges of the complete graph K6K_{6} can be coloured blue and yellow in such a way that there are precisely nn monochromatic triangles?

Typos? Please submit corrections to this page on GitHub.