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 2 of 6: Track degrees and the edge count

Previous step Next step

\deg'(A)=\deg(A)-2,\qquad \deg'(B)=\deg(B),\qquad \deg'(C)=\deg(C),\qquad |E'|=|E|-1

Detailed analysis

In a toggle at $A,B,C$ , vertex $A$ loses both edges $AB$ and $AC$ , so its degree drops by exactly $2$ and its parity is unchanged. Vertex $B$ loses edge $AB$ but gains edge $BC$ , and vertex $C$ loses $AC$ but gains $BC$ , so their degrees do not change at all. Every other vertex is untouched. Hence a toggle always removes exactly one edge from the graph, and it never changes the parity of any vertex's degree.