2019 IMO 第 3 题

A social network has 2019 users, some pairs of which are friends (friendship is symmetric). If $A$ , $B$ , $C$ are three users such that $A B$ are friends and $A C$ are friends but $B C$ is not, then the administrator may perform the following operation: change the friendships such that $B C$ are friends, but $A B$ and $A C$ are no longer friends.

Initially, 1009 users have 1010 friends and 1010 users have 1009 friends. Prove that the administrator can make a sequence of operations such that all users have at most 1 friend.

一个社交网络有 2019 个用户，其中一些是朋友(友谊是对称的)。如果$A$、$B$、$C$是三个用户，$A B$是好友，$A C$是好友，但$B C$不是好友，则管理员可以执行以下操作：更改好友关系，使得$B C$是好友，但$A B$和$A C$不再是好友。

最初，1009 个用户有 1010 个朋友，1010 个用户有 1009 个朋友。证明管理员可以进行一系列操作，使得所有用户最多有 1 个好友。