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?

  • 0
    Consider that you're trying to end up with either a red or blue triangle. How could that happen if no two adjacent edges had the same colour? Also, you need at least three colours already for a proper edge-colouring of $K_3$ (a triangle), so there's no way you can get a proper edge-colouring of $K_6$ with only two colours.2012-04-26
  • 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