Why the Ramsey number $R(2,4)$ is not equal to $2$?

1k Views Asked by At

I'm reading Harris/Hirst/Mossinghoff's: Combinatorics and Graph Theory. Here:

enter image description here

I don't understand: For all $2$-colorings, it must have a $K_p$ and $K_q$ or it must have a $K_p$ or a $K_q$? I'm confused: If it's the second option, a $K_2$ does have a $K_2$. But it's not clear that it actually speaks as if it were the first option.

2

There are 2 best solutions below

5
On BEST ANSWER

You're missing the requirement that the $K_p$ or $K_q$ must be completely red and blue, respectively.

$R(2,4)$ must be larger than $2$ because if you color the single edge in $K_2$ blue, then the resulting graph does not contain a red $K_2$, and does not contain a blue $K_4$ either.

0
On

You can always prevent one of them by colouring all edges the same color. Therefore it must be (inclusive) or. This gives, for instance, $R(2,n)=n$, since if there are $n$ vertices, then either you have a $K_2$ of one color, or all edges are of the second color and you have $K_n$ in that color.

I think maybe the important point you've missed here is that the order matters, in some sense. The first number is coupled to the red subgraph and the second number to the blue one.