In a group of $97$ students, those who know the same amount of people are placed in the same group, what is the smallest number of students in the largest group?
Let's show the student as vertices.
We can clearly see that, the number of degrees in every group can't all be different. So the answer can't be $1$. Now, I'll try to check if the answer is $2$.
$2$ people and they know some $K$ people. And the other $95$ must all have different degrees.
Enumerate every vertices $1$ through $97$.
Let $u$ be our current vertice. For every $u \leq 48$, connect $u$ with all $v \in [u + 1, 98 - 2 \cdot u]$, and that will give us the below graph. In this graph $u = 49$ and $u = 50$ have $48$ degrees both and that's because $u = 49 $ and $u = 50$ is connected with $\{1, 2, \cdots ,48\}.$
Also vertices $u = 51$ has degree $47$ and $u = 97$ has $1$. Degree of every vertices between is decreasing one by one. That means we've used all $96$ degrees.
So the answer is $2$ and we have a construction. But I wasn't able to come up with this when solving it and had to get help. First of all, is there a flaw in this logic? Then if you have a better solution, can you tell me about it? And at last, any similar problems you might know? It would also be very helpful if you could tell me about similar techniques.
The pigeonhole principle shows you cannot have everybody with a different number, as you would need one person knowing everybody else and one person knowing nobody else, a contradiction.
(Corrected from earlier) A similar but perhaps simpler example of where the largest group is $2$ would be where person $n$ knows everybody else from person $97-n$ up to person $97$. Since there is no $0$, you have people $96$ and $97$ knowing everyone else, i.e. a pair knowing the same number of people. You also have people $48$ and $49$ knowing everybody else from $48$ to $97$, so another pair. Everybody else knows a different number of people. There will be other examples.