1
$\begingroup$

I'm trying to understand a proof:

$R(3,3) = 6$

proof:

Take a red/blue colouring of $K_6$. Take a vertex $v$ (is an element of) $V(K_6)$, either $v$ is incident to $\geq 3$ red edges or, $v$ is incident to $\geq 3$ blue edges.

Without loss of generality, the former holds. Consider the other endpoints of these edges, either $2$ of them are joined by a red edge - so we have a red $K_3$ - or they are all joined by blue edges and we get a blue $K_3$. Hence $R(3,3)=6$.

Now, this is simple enough, but what is confusing me is the construction of the edge colouring. I thought that, like vertex colouring, we coloured the edges so that no two adjacent edges had the same colour. But here, in the first part of the proof to obtain a red $K_3$, adjacent edges are coloured red, and in the second part of the proof adjacent edges are coloured blue!

Could someone please explain this to me, maybe I am missing a tidbit of vital knowledge of the rules of edge colouring?

  • 2
    Aside: This argument does *not* prove that $R(3,3)=6$. It proves that $R(3,3) \le 6$. To complete the proof you need to exhibit a red/blue edge colouring of $K_5$ with no monochromatic triangle.2012-04-26

2 Answers 2

3

In Ramsey theory two incident edges may have the same color. It's a different problem than that of edge coloring of a graph.

1

In the Ramsey theory (for graphs), edge colorations not necessary must be those whose incident edges have different colors, instead we consider all possible edge colorations, in the case of $R(K_3,K_3)$, all possible two edge colorations.

To obtain the lower bound of $R(K_3,K_3)$ is sufficient to note that $K_5$ can be factorized into two edge disjoint cycles.