IIT JEE , AIEEE Forum - Mathematics , Algebra

titun

There is a commitee of five people. Any two of them are either friend or enemies. No three of them are friends or enemies. Prove that each people in the community can have exactly two friends.

I'll give a salute if you can solve it and can make me understand your solution.

amar.gupta

Dear,

LET 5 members are A,B,C,D,E . now out of 5 we select A .

now there are 4c2 = 6 groups of 3 members can be formed which has A as one member.

ABC, ABD , ABE , ACD ,ACE ,ADE

we suppose A has more than 2 friends let say 3 friends as B,C,D .

so In group ABC since (A, B) and (A ,C) are friends so (B,C) should be enemy.

now In group ABD since (A, B) and (A ,D) are friends so (B,D) should be enemy.

similarly In group ACD since (A, C) and (A ,D) are friends so (C,D) should be enemy.

now consider group of BCD , here all there are enemy to one another.

which is not possible.

so our assumption is wrong and no body could have more than two friends.

now each is having exactly two friends.so they must have exactly two enemies.

A is having two friends as B,C and two enemies as D,E .So B and C should be enemy.

now consider ADE , so D,E should be friends.

now let B has D as friend and E as enemy.

consider BCE , so C and E should be friend. and C and D should be enemy.

Summary:

            Friend              Enemy
A           B,C                  D,E

B           A,D                   C,E

C           A,E                    B,D

D           B,E                    C,A

E           C,D                     A,B

now you consider any group , all conditions satisfy.

Ask & Discuss Questions with Community & Experts