The Gateway to Computer Science Excellence
+1 vote
44 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
in Mathematical Logic by
retagged by | 44 views

1 Answer

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

by Loyal
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
60,009 answers
201,233 comments
94,693 users