IMC 2009 · Problem 3

In a town every two residents who are not friends have a friend in common, and no one is a friend of everyone else. Let us number the residents from $1$ to $n$ and let $a_i$ be the number of friends of the $i$-th resident. Suppose that $\sum\limits_{i=1}^{n} a_i^2 = n^2 - n$. Let $k$ be the smallest number of residents (at least three) who can be seated at a round table in such a way that any two neighbors are friends. Determine all possible values of $k$.