This problem came from a Putnam problem solving seminar.
If each person in a group of n people is a friend of at least half the people in the group, then show that it is possible to seat the n people in a circle so that everyone sits next to friends only.
My idea was to use induction on $n$; if $n$ is odd we can remove a person, note that the remaining $n-1$ people all have at least $n/2$ friends left, use our inductive hypothesis to seat them, and then use the pigeonhole principle to seat the last person.
Unfortunately, this doesn't work when $n$ is even because after removing a person, some of the remaining people might have less than $n/2$ friends left. In fact, my friend who actually participated in the seminar said they had the same issue, but didn't address it because they ran out of time.
Is this sort of induction a reasonable approach? If so, how would we deal with the case when $n$ is even? If not, what's a better way to think about the problem?
P.S. I'm not sure of the best tags for this question, so please feel free to re-tag if necessary.