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 1 of 6: Model friendships as a graph

Previous step Next step

G=(V,E),\quad |V|=2019,\qquad \text{toggle}(A,B,C):\ AB,AC\in E,\ BC\notin E\ \longmapsto\ E'=(E\setminus\{AB,AC\})\cup\{BC\}

Detailed analysis

Let $G=(V,E)$ be the graph with $V$ the $2019$ users and $E$ the friendship pairs. Call the described change a toggle at $A,B,C$ : it needs edges $AB$ and $AC$ present but $BC$ absent, and it replaces $E$ by $E'=(E\setminus\{AB,AC\})\cup\{BC\}$ . The goal becomes reaching a graph in which every vertex has degree at most $1$ .