How many people can be in a group where everyone has exactly 3 acquaintances, and two people have exactly one mutual acquaintance if and only if they do not know each other?
Solution. We represent the acquaintance system with an undirected graph, where people are the vertices, and two vertices are connected by an edge if and only if the corresponding people know each other. According to the problem, the degree of every vertex is 3. In any graph, the sum of the degrees of the vertices is even, so the number of people in the group can only be even. Any two people either know each other or have a common acquaintance. Therefore, if we select someone, they have 3 acquaintances, and each of these 3 acquaintances has 2 more acquaintances (who may not necessarily be distinct from each other). This represents at most \(1+3+6=10\) people. Thus, the number of people can only be \(2, 4, 6, 8,\) or \(10\).

Among these, 2 is clearly not possible.

4 is also not possible, because in this case, only a complete graph can have every vertex with a degree of 3, but then everyone would know everyone else. The numbers 6, 8, and 10 are possible (the vertices of the graph are represented by solid squares):
![](https://cdn.mathpix.com/cropped/2024_05_02_a9f1bf56a8e63f18b5dcg-1.jpg?height=244&width=718&top_left_y=564&top_left_x=694)

Therefore, the group can have 6, 8, or 10 members.