2019 IMO Shortlist C5

On a certain social network, there are 2019 users, some pairs of which are friends, where friendship is a symmetric relation. Initially, there are 1010 people with 1009 friends each and 1009 people with 1010 friends each. However, the friendships are rather unstable, so events of the following kind may happen repeatedly, one at a time: Let $A, B$, and $C$ be people such that $A$ is friends with both $B$ and $C$, but $B$ and $C$ are not friends; then $B$ and $C$ become friends, but $A$ is no longer friends with them. Prove that, regardless of the initial friendships, there exists a sequence of such events after which each user is friends with at most one other user. (Croatia)

在某个社交网络上，有 2019 个用户，其中一些是朋友，其中友谊是对称关系。最初，有 1010 人，每人有 1009 个朋友，还有 1009 人，每人有 1010 个朋友。然而，友谊相当不稳定，因此以下类型的事件可能会一次一个地重复发生：设$A、B$和$C$是人，$A$与$B$和$C$都是朋友，但$B$和$C$不是朋友；然后$B$和$C$成为朋友，但$A$不再是他们的朋友。证明，无论最初的友谊如何，都存在一系列此类事件，之后每个用户最多与另一个用户成为朋友。 (克罗地亚)