It is given that each person in the group of n persons has at least half of the persons in the group as his friends.It is required to prove that it is possible to seat them in a circle so that everyone sits next to a friend of his or hers.Here,I have tried to prove the statement by induction .
PROOF:If there are 3 persons in the group, then the statement is easily verifiable. Let there be k(k is even) persons in the group such that they can be seated in a circle in the desired order.Now,if there are k+1 persons in the room then k of them can be still seated in a circle such that the desired order is achieved. Now,it is required to seat the (k+1)th person in the circle such that the order is retained. According to the statement, the (k+1)th person will have at least (k+2)/2 friends in the circle. Let it be assumed that none of his friends share a common friend in the circle or sit beside each other. If this is so, then there are at least (k+2)/2 persons in total that sit beside (k+2)/2 of the (k+1)th persons friend. Thus,togetherly,there are at least k+2 persons seated in the table.This contradicts the fact that there are k persons in the circle. Hence,at least two of his friends share a common friend in the circle or sit beside each other. If one denotes the (k+1)th person by M , his friends as G1 and G2 then for G1 and G2 sitting beside each other M can be seated in between them and for G1 an G2 sharing a common friend C, then M can be seated in between C and G2. This completes the proof.
I am doubtful about the accuracy of the proof.Please help me to verify that it is correct.If it is wrong,please help me improve it.This proof covers only the case in which k is even.However,as per the given reply,this doesnt hold for the case in which k is odd.