# Cuboid room, hooks and strings proof

I'm trying to do the following problem:

In a cuboid shaped room a hook is placed in the centre of each wall, the floor, and the ceiling. Every pair of hooks has either a piece of red or blue string tied between them. As this task is being performed triangles will be formed between sets of three hooks with edges being red or blue.

Prove that it is impossible to complete this task without forming at least one triangle of the same colour.

I am totally stuck and have been for some hours (although by the rated difficulty it should not be that hard :( ).

What I've concluded is that there's: 6 hooks, 15 strings and 20 triangles. I, however, can't find any way to prove that at least one triangle should have the same color.

I've tried creating a map of all the strings and triangles but this very quickly becomes really confusing so that's not the way to go.

Hints are very much appreciated.

• Google 'Ramsey numbers'. – TokenToucan Jan 9 '16 at 22:07

The proof benefits from a picture - if we assume there is no such triangle, the PHP guarantees that one of the nodes will either be in a triangle or induce a triangle in its neighbors, so we have a contradiction. Suppose we have the given situation ($6$ nodes, every possible edge colored either blue or red). Assume that there is no such triangle, and we will arrive at a contradiction. Work with a fixed node/hook $v$. By the (strong) pigeonhole principle, there are at least $3$ strings of one color extending from this node; WLOG, let this color be blue and three nodes they reach be $w_1,w_2,w_3$. By hypothesis, none of $w_1,w_2,w_3$ can be connected to each other by a blue string because this would give a blue triangle $\{v,w_i,w_j\}$ contradicting the hypothesis. This means they are all connected by red string, but that gives a red triangle $\{w_1,w_2,w_3\}$ so we arrive at a contradiction. Then our hypothesis was incorrect, so there must be some triangle that with all blue or all red edges.