The Gateway to Computer Science Excellence

+1 vote

In a group of five people one is either a friend or enemy of the others. It is given that no three of them are friends and no three of them are enemies. Prove that every member in that group has exactly two friends

+1 vote

Best answer

Suppose there exist a person in the group who has either three friends or one friend.

Now,since every person in the group is either a friend or enemy of the others so having only one friend means he has three enemies.

Now, construct a graph where the persons are represented by nodes and edges are joined between the nodes iff they are friends. Let the graph be named as G.

Assume that the node A has three friends B, C and D

Since no three of them are friends there will not exist any triangle in G.

Since A,B and A,C are friends B,C can't be friends anymore otherwise there would be a triangle in G.

Since A,B and A,D are friends B,D can't be friends anymore otherwise there would be a triangle in G.

And since A,C and A,D are friends C,D can't be friends anymore otherwise there would be a triangle in G.

So, we get that B,C and D are enemies but it is given that no three of the group are enemies.

Hence contradiction so, A can't have three friends.

Since A is chosen arbitrarily so none of the members of the group would have three friends.

Now, assume A has only one friend. Then A will have three enemies.Then the graph G' ( complement of G ) would contain three edges from A. Same reasoning as above (just replace friends with enemies) would show that A can't have three enemies either.

So, no one in that group can have only one friend.

So, every member in that group has exactly two friends.

52,215 questions

60,009 answers

201,233 comments

94,693 users