
2. There are $n$ guests at a party. Any two guests are either friends or not friends. Every guest is friends with exactly four of the other guests. Whenever a guest is not friends with two other guests, those two other guests cannot be friends with each other either.

What are the possible values of $n$ ?


2. We first consider the friends of one guest, say Marieke. We know that Marieke has exactly four friends at the party, say Aad, Bob, Carla, and Demi. The other guests (if there are any other guests) are not friends with Marieke. Hence, they cannot have any friendships among themselves and can therefore only be friends with Aad, Bob, Carla, and Demi. Since everyone has exactly four friends at the party, each of them must be friends with Aad, Bob, Carla, and Demi (and with no one else).

Since Aad also has exactly four friends (including Marieke), the group of guests that are not friends with Marieke can consist of no more than three people. If the group consists of zero, one, or three people, we have the following solutions (two guests are connected by a line if they are friends):
![](https://cdn.mathpix.com/cropped/2024_04_17_97e5f9f1aa9885a35eabg-1.jpg?height=348&width=1260&top_left_y=2239&top_left_x=406)

Solutions with five, six, and eight guests in total.

Now we will show that it is not possible for this group to consist of two people. In that case, Aad would have exactly one friend among Bob, Carla, and Demi. Assume, without loss of generality, that Aad and Bob are friends. In the same way, Carla must be friends with one of

Aad, Bob, and Demi. Since Aad and Bob already have four friends, Carla and Demi must be friends. However, since they are both not friends with Aad, this contradicts the requirement in the problem statement.

We conclude that there can be five, six, or eight guests at the party. Hence, the possible values for $n$ are 5,6 , and 8 .

