1
$\begingroup$

Could I get any help with this one, I'm lost.

We know that the Ramsey number $R(3, 3)$ equals $6$. Suppose the edges of a complete graph of $10$ vertices are coloured each either blue or red. Show that there is a blue triangle or a red tetrahedron (i.e. a complete graph on 4 vertices all of whose edges are coloured red). [Try to use the pigeonhole principle with unequal parts.]

$\endgroup$
5
$\begingroup$

Hints:

1) assume one vertex has six outgoing red edges. Consider the 6-vertex graph madd by the corresponding vertices.

2) assume one vertex has four outgoing blue edges. What happens if there is a blue edge between two of the corresponding vertices? What happens if there is no blue edge?

$\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.