Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
6  
This is a standard small example of Ramsey's theorem. –  Henning Makholm Nov 21 '11 at 19:11
1  
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
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
yes i have not considered complete graph,by using pigenhole priciple everything is clear –  dato datuashvili Nov 21 '11 at 19:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.