# graph coloring problem

today my mathematic's lecturer asked me following question proof that if in 6 man,there is not possible to search such 3 man who knows each other,then there always could be found such 3 man who does not know each other

firstly i was thinking that it was identity,(like 5=5)but then he said to me considering this problem using graph (6 vertices),i was trying today to draw such graph and get counterexample,i have considered that 3 man know each other if there are connected by same color edge and is created triangular form,but i dont understand if it is theorem then why i got opposite?thanks a lot

-
This is a standard small example of Ramsey's theorem. – Henning Makholm Nov 21 '11 at 19:11
To take your idea of drawing a "counterexample" a bit further, consider that the graph is complete on six vertices. There are two colors for the edges, one for a pair of men who know each other and one for a pair of men who don't. The claim is that there will always be a triangle of three same-colored edges. (It is true.) – hardmath Nov 21 '11 at 19:31

Hiint: Consider the complete graph on $6$ points as representing the men, coloring each edge red if the two men know each other and blue if they do not. You are asked to prove that if there is no red triangle, there is a blue triangle. Pick one man and think about the possibilities for the color of his outgoing $5$ edges...