Showing that there exists three points, joined by lines of the same colour Every one of six points is joined to every other one by either a red or a blue line. Show that there exists three of the points joined by lines of the same colour. I'm not sure how to do this. We haven't learnt any combinatorial methods yet, and this is just inside the problem set under the Proofs topic. All I know is that there will be $5+4+3+2+1=15$ lines in total.

Choose one point, and call it $p$. Then, from $p$ to other points, there are five lines, each being possibly one of two colors. Clearly, at least three of them must be of the same color, say red. Let these go to the points $a,b,c$.

Case 1: If any one of $ab,bc$ or $ca$ is coloured red, then the triangle $abp,bcp,cap$ will have all red coloured sides respectively.

Case 2: If none of these sides is coloured red, these are coloured blue, hence the triangle $abc$ is blue.

Hence, either way we have a blue or red coloured triangle.

The interesting thing is, that with five vertices this is not necessarily true.

Moreover, it is worth asking what would be the minimum number of vertices for which a triangle will be a certainty if there were three colours involved, say red,blue,green.

This is all part of the study field of Ramsey Theory.