2019 IMO Problems/Problem 3
Problem
A social network has 
users, some pairs of whom are friends. Whenever user 
is friends with user 
, user is also friends with user . Events of the following kind may happen repeatedly, one at a time:
Three users , , and 
such that is friends with both and , but and are not friends, change their friendship statuses such that and are now friends, but is no longer friends with , and no longer friends with . All other friendship statuses are unchanged.
Initially, 
users have 
friends each, and users have friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.
