Nov 14, 2009

6 people in a group

 Prove that in a group of six people, there will always be three people that are mutual friends or mutual strangers. (Assume that “friend” is symmetric-if is a friend of y, then y is a friend of x.)




1 comment:

  1. Consider the 6 people as points in a plane and join two people with a line who are friends. So we get an undirected graph for this. Now we have to prove that either there is a triangle in this graph or there are three disjoint points.Now either in the graph G or in G-complement there any given point will have 3 friends. ( Complement of a graph is found by joining the unconnected edges and removing the connected ones). Now if any two these two are friends then we get a triangle else these three are mutually disjoint. And mtually disjoint means a triangle in the complement and vice versa.

    ReplyDelete