Ukrainian National Mathematical Olympiad

a) Denote Mykhailyk and Vitalyk by $A$ and $B$ respectively. Let $M(A)$ and $M(B)$ be the sets of acquaintances of $A$ and $B$ respectively (see Fig. 3).

There is no person in $M(A)$ that knows $B$, since in this case $A$ and $B$ would have a common acquaintance. So every person $X$ from $M(A)$ has exactly two common acquaintances with $B$. One of them is $A$, and the other person, call him $Y$, belongs to the set $M(B)$. In this way for every person $X$ from the set $M(A)$ we assign exactly one person $Y$ from $M(B)$. It is easy to see that this correspondence is one-to-one, and so the numbers of people in $M(A)$ and $M(B)$ are the same.

b) Example given on Fig. 4 shows that the situation described in the problem statement can happen when there are exactly 6 people on the party.

Fig. 3 Fig. 4