# why is the Ramsey number $R(3,4)$ not equal to $R(3,3)$?

I understand why R(3,3) is equal to 6 since we have a clique of 3 in a graph of 6 vertices. What I don't understand is that by definition of Ramsay number it says that for a R(r,s) we have to find a clique of either 3 or 4 in size. In this case, we can find a clique of 3 in a graph of 6 nodes unconditionally. Could someone explain to this hopeless student why R(3,4) = 9?

• You are misunderstanding the definition of R(r,s). The definition of R(3,4) is that for any coloring of edges of a complete on this many vertices with red and blue, we will have either a red clique on 3 vertices or a blue clique on 4 vertices. The reason this needn't be the same as R(3,3) is that the colored graph may contain a blue clique on 3 vertices, but no red clique on 3 vertices, or blue clique on 4 vertices. Indeed, it might be instructive for you to find such a coloring of a complete graph on 6 vertices. Dec 25, 2020 at 19:49
• I don't really understand since it is possible to find a clique of 4 nodes on K_6 where as you say it isn't possible which makes me slightly confused. Dec 25, 2020 at 20:02

For $$R(3,4)$$ you must find either a clique of size $$3$$ or an independent set of size $$4$$. The graph

   *    *    *
|    |    |
*    *    *


on $$6$$ vertices has neither a clique of size $$3$$ nor an independent set of size $$4$$. Every set of $$3$$ vertices contains two that are not adjacent, and every set of $$4$$ vertices contains two that are adjacent.

• so from what i understand R(r,s) means that if there is an r clique there must therefore be an independent set of size s? Dec 25, 2020 at 20:03
• @a_confused_student: No, $R(r,s)$ is the smallest $n$ such that every graph on $n$ vertices has either an $r$-clique or an independent set of size $s$ (or both). Dec 25, 2020 at 20:20
• but in the example given we have an independent set of size 3 and so for R(3,4) we can say that for n= 6 we satisfy the definition you gave. I'm really sorry for giving so much trouble i'm really confused with all these definitions haha Dec 25, 2020 at 20:49
• @a_confused_student: No, it does not satisfy that definition. It does not have a $3$-clique, and it does not have an independent set of size $4$. You cannot interchange the two numbers. Dec 25, 2020 at 20:56