Gathering problem I thought I had a proper solution for the following problem, but my teacher said it's wrong. I have no idea/clue how to do it in a different, correct way.
There gathered n people in a room. At the beginning of this meeting every person had exactly 3 friends among the rest in the room. During the meeting some people met each other. When the meeting ended, every person had exactly 4 friends among the rest. Find all n numbers for which this situation is possible (we assume, that if person A knows person B, then person B knows person A).
Best regards,
Tom.
 A: First note that the initial graph is 3-regular, and so $3n = 2m$ where $n$ is the number of vertices and $m$ is the number of edges (acquaintances). Thus $n$ is even. Clearly $n > 4$ because $4$ is too few to have $4$ acquaintances. Now the problem is to find a solution for any even $n$ that is at least $6$.
The trick is to find a solution for each $n$ in $(6,8,10)$, because you can combine them to get a solution for any larger $n$, because $6+6k = (k+1)(6)$ and $6+6k+2 = k(6)+8$ and $6+6k+4 = k(6)+10$, for any $k \in \mathbb{N}$. It should not be too hard to find solutions for the three base cases with some trial and error.
A: In terms of diagrams to begin to build intuition, this is the kind of thing I was thinking about, showing regular graphs for low integers. (A regular graph being a graph where every vertex has an equal local degree, i.e., number of edges.) You can see there are no solutions for $n < 6$ or for $n = 7$.

This is an intriguing problem. Doing some research I was surprised to find that we have no closed formula for the number of regular graphs of $n$ vertices with $m$ edges, just an asymptotic one.
