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 4 of 6: The starting network is connected, not a clique, and can never become a cycle

Previous step Next step

1009+1009+2>2019,\qquad \deg(A_0)=1009\ (\text{odd, invariant under toggles})\ \Longrightarrow\ G\ \text{never becomes a cycle}

Detailed analysis

Every user has degree $1009$ or $1010$ , so any two non-adjacent users have neighbor counts summing to at least $1009+1009>2019-2$ , forcing a common neighbor by pigeonhole; hence the initial graph $G$ is connected. It is not a clique, since a clique on $2019$ vertices needs degree $2018$ . By Step 2, only one vertex's degree changes at each toggle, and only by $2$ , so the parity of every vertex's degree is fixed forever; a vertex that starts with odd degree $1009$ can never reach the even degree $2$ that a cycle would require of it, so $G$ can never become a cycle. By Step 3, we may keep toggling $G$ while it stays connected and is not yet a tree, and each such toggle strictly decreases the edge count, so this process must stop: it stops exactly when the graph has become a spanning tree on all $2019$ vertices.