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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Tara B
    Apr 26, 2012 at 9:37
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 26, 2012 at 9:40

2 Answers 2

3
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.