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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .