+1 vote
37 views
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
retagged | 37 views

+1 vote

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.

selected

2