Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to understand a proof:

$R(3,3) = 6$


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?

share|cite|improve this question
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. – Tara B Apr 26 '12 at 9:37
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. – Chris Eagle Apr 26 '12 at 9:40

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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