Problem 3

A social network has

2019

users, some pairs of whom are friends (friendship is a symmetric relation). Events of the following kind may happen repeatedly, one at a time: three users

A

B

, and

C

such that

A

is friends with both

B

and

C

, but

B

and

C

are not friends, change their friendship statuses such that

B

and

C

are now friends, but

A

is no longer friends with

B

, and no longer friends with

C

. All other friendship statuses remain unchanged. Initially,

1010

users have

1009

friends each, and

1009

users have

1010

friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.

Step 6 of 6: Terminate at a matching

Previous step Next step

|E_{t+1}|=|E_t|-1,\qquad \text{no legal toggle}\Longleftrightarrow\ \deg(v)\le 1\quad\text{for every }v

Detailed analysis

Continue making any legal toggle in the current forest. Each one reduces the edge count by $1$ , so the finite process must terminate. At termination, if some vertex $A$ had two neighbors $B,C$ , acyclicity would imply $BC$ is absent, giving another legal toggle; hence every vertex has degree at most $1$ . Thus the final friendship graph is a matching together with isolated vertices, exactly as required.