The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+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
asked in Mathematical Logic by (305 points)
retagged by | 37 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. 

answered by Loyal (9.5k points)
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
49,811 questions
54,540 answers
188,429 comments
75,603 users