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.
Best Answer
This is known as Dirac's theorem. I don't know if an inductive proof is possible; the standard proof is extremal. You consider the longest sequence of friends and show by contradiction that it must be a Hamiltonian circuit. I can edit with more details if you want the full argument; it's quite nice.
Edit: the argument is as follows. It can be found, for example, in Bollobas' Modern Graph Theory (p. 106). First let's establish the graph-theoretic language. Let $G$ be a graph on $n$ vertices, $n \ge 3$. For each $v \in G$ let $d_v$ denote the number of neighbors of $v$. Then the claim is that if $d_v \ge \frac{n}{2}$ for each $v \in G$, then $G$ is Hamiltonian.
We claim that $G$ is connected. Indeed, if $v, w \in G$ then $v$ and $w$ each have $\frac{n}{2}$ neighbors out of a possible $n-1$, so they must share some neighbor. (This step works under the weaker assumption that $d_v + d_w \ge n$ for each $v \neq w$.)
Now suppose that $G$ is not Hamiltonian. Let $v_1, ... v_k$ be a path all of whose vertices are distinct with $k$ maximal. Then $v_1$ and $v_k$ have no neighbors outside the path (by maximality), so all of their neighbors must be one of $v_1, ... v_k$. In addition, $v_1$ cannot be connected to $v_k$; otherwise we would have a cycle of length $k$, and by connectivity this cycle would be connected to some $w$ not in the cycle, giving a path of length $k+1$, which contradicts maximality.
More generally, $v_1$ cannot be connected to a vertex $v_{i+1}$ with the property that $v_i$ is connected to $v_k$, since otherwise $v_{i+1} v_1 v_2 ... v_i v_k v_{k-1} ... v_{i+2}$ is a cycle of length $k$. It follows that the sets $\{ v_i : v_1 \sim v_i \}$ and $\{ v_{i+1} : v_i \sim v_k \}$ are disjoint subsets of $\{ v_2, ... v_k \}$, but by assumption their union must have size at least $n$ (this step also works under the weaker assumption that $d_v + d_w \ge n$ for each $v \neq w$); contradiction.