Graph Theory: Prove Ramsey Number $R(3, 4)=9$

2.8k Views Asked by At

Most of the proofs I've seen prove this by showing that $R(3, 4) \leq 9$ and at the same time $\geq 9$. The former one is natural and easy to understand. To prove $R(3, 4) \geq 9$, a lot of proofs construct a graph with $8$ vertices which contains no $K_4$ and whose complement contains no $K_3$. The counterexample is often like this counterexample.

As far as I know, $R(m, n)=R(n, m)$, so if I want to show that $R(3, 4) \geq 9$, the graph I construct should not contain any monochromatic $K_3$ or $K_4$. Go back to the counterexample. Though there is no blue $K_4$ and red $K_3$, it can be easily found that there are blue $K_3$s in the first graph. Is the counterexample wrong? Or is there any problem with my understanding about Ramsey Number? Thanks a lot for the help.

1

There are 1 best solutions below

0
On BEST ANSWER

The counterexample is correct. Note it's not the graph itself not containing $K_n$ and $K_m$:

If we say $R(n,m) = k$, then this means every graph $G$ with $k$ vertices, either $G$ contains a $K_n$ or the complement $G'$ contains a $K_m$. If we want to show $R(n,m) > k$, then we show that there exists some graph $G$ with $k$ vertices that fails that condition, namely $G$ does not contain $K_n$ and $G'$ does not contain $K_m$. We just need to find one such example.

Since in the counterexample you found, the 8-vertex graph $G$ (blue) has no $K_4$ and its complement $G'$ (red) contains no $K_3$, we see that $R(4,3)>8$. Now it is true that $R(4,3)=R(3,4)$: To show $R(3,4)>8$ as well, notice the graph $G'$ (red) has no $K_3$ and its complement $G''=G$ (blue) has no $K_4$.