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 x is a friend of y, then y is a friend of x.)
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.
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