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 5 of 6: Toggle inside the tree without creating a cycle

Previous step Next step

T\text{ a tree},\quad AB,AC\in E(T),\ BC\notin E(T)\Longrightarrow\ T'=(T\setminus\{AB,AC\})\cup\{BC\}\text{ is a forest}

Detailed analysis

Now let $T$ be the spanning tree obtained above. Whenever a vertex $A$ has two neighbors $B,C$ , the unique path from $B$ to $C$ is $B-A-C$ , so $B$ and $C$ are not adjacent and the toggle is legal. Removing $AB$ and $AC$ from the tree separates it into three components, and adding $BC$ joins the two components containing $B$ and $C$ ; therefore the result is a forest (with one fewer edge) and no cycle is created. The same argument applies to every later forest.