Question 77
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.
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.