59th Ukrainian National Mathematical Olympiad

We are going to show that the acquaintances graph has no odd cycles. For the sake of contradiction, let us take the smallest odd cycle. Clearly, there are no edges connecting vertices of this cycle (as it would divide the cycle into two smaller cycles, at least one of which would be odd). Next, let us enumerate people from $1$ to $2k+1$ along the cycle and use the statement for people with numbers $1$, $2$, $3$, $k+2$, $k+3$ (one can easily check that they are pairwise distinct). Note that there cannot be edges between any three people having the common acquaintance, because it would lead to the existence of a triangle. Hence, if $2k+1=5$, there would be such edges between people $1$, $2$, $3$, $k+2$, $k+3$, so $k>2$. Then there must be a common acquaintance for $1$, $3$, and one of $k+2$, $k+3$, w.l.o.g. let $1$, $3$, $k+2$ have the common acquaintance. From here one can easily construct a smaller odd cycle by using the common acquaintance $X$ of $1$ and $k+2$ ($X$ doesn't belong to the original cycle), namely $1$, $2$, $3$, $\dots$, $k+2$, $X$ and $k+2$, $k+3$, $\dots$, $2k+1$, $1$, $X$. Both of them are smaller than the original cycle and have lengths of different parity, leading to the contradiction.