2

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.

snehamayee sahu
  • 93
  • 6

1 Answers1

2

What if $k=3$, and you have $4$ people, $A,B,C$, and $D$, such that $A$ is friends with $D$ and $B$, $B$ is friends with $A$ and $C$, $C$ is friends with $B$ and $D$, and $D$ is friends with $C$ and $A$? When you remove any one of them, $2$ of the remaining $3$ people have only one friend, so the induction hypothesis doesn’t apply. To make an argument by induction, you would first have to show that you can always remove one person in such a way that the remaining group satisfies the induction hypothesis.

I suggest treating it as a problem in graph theory: each person is a vertex, and two vertices (people) are joined by an edge if they are friends. Then the result follows from Ore’s theorem.

Brian M. Scott
  • 616,228