Ramsey Numbers r(2, n) = n

5.9k Views Asked by At

How do you prove that r(2, n) = n in Ramsey numbers? We have to show that r(2,n)<=n and that r(2,n) >= n.

1

There are 1 best solutions below

0
On

To show that $R(2,n) \leq n$ consider the clique on $n$ vertices $k_{n}$, and colour its edges in two colours (blue and red), if there is atleast one blue edge then you have a monochromatic $k_{2}$, otherwise all edges are coloured red which means your graph is a monochromatic $k_{n}$.

To see the that $R(2,n) \geq n$ it'll suffice to show that there exists a colouring of $k_{n-1}$'s edges such that there is no blue $k_{2}$ or a red $k_{n}$. Indeed, consider the colouring which gives the red colour to all edges.