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

159 Views Asked by At

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.]

1

There are 1 best solutions below

0
On

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?