A social network has $2019$ users, some pairs of whom are friends. Whenever user $A$ is friends with user $B$, user $B$ is also friends with user $A$. 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 are 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 (Operation analysis): When user $A$ (with friends $B,C$ where $B,C$ are not friends) triggers an event, $A$ loses 2 friends, $B$ and $C$ each lose 1 friend (losing $A$) but gain 1 friend (gaining each other). So $\mathrm{deg}(A)$ decreases by 2, while $\mathrm{deg}(B)$ and $\mathrm{deg}(C)$ are unchanged.

Step 2 (Monovariant): Consider $\Phi ={\sum }_v\mathrm{deg}(v{)}^2$. After one operation, $\mathrm{deg}(A)\to \mathrm{deg}(A)-2$, so the change in $\Phi$ is $(\mathrm{deg}(A)-2{)}^2-\mathrm{deg}(A{)}^2=-4\mathrm{deg}(A)+4<0$ whenever $\mathrm{deg}(A)\ge 2$. The monovariant strictly decreases with every operation (and an operation is possible whenever some vertex has degree $\ge 2$ with two non-adjacent neighbors).

Step 3 (Parity invariant): The total number of edges changes: we remove 2 edges ($AB$, $AC$) and add 1 edge ($BC$), so the number of edges decreases by 1 each operation. Initially, the total degree is $1010\times 1009+1009\times 1010=2\times 1010\times 1009$, so there are $1010\times 1009=1,019,090$ edges.

Step 4 (Termination and target): Since $\Phi$ is a nonneg integer that strictly decreases, the process terminates. At termination, every vertex with $\mathrm{deg}\ge 2$ must have all its neighbors mutually adjacent (forming a clique among neighbors). We need to show termination gives $\mathrm{deg}\le 1$.

At a terminal state, every connected component is a clique (since if $A$ has neighbors $B,C$ with $B,C$ not friends, we could still operate). In a clique of size $k$, each vertex has degree $k-1$.

Step 5 (Parity argument): Each operation decreases the edge count by 1, so the terminal edge count has the same parity as $1,019,090$, which is even. A matching on $2019$ vertices has at most $1009$ edges. We verify that the process can reach a state of all cliques of size $\le 2$: observe that in a clique of size $k\ge 3$, we can pick any $A$ and two of its neighbors $B,C$ and perform the operation (since $B$ and $C$ are friends in a clique — wait, they ARE friends, so the operation requires $B,C$ NOT friends).

So actually at a terminal state, every vertex with $\mathrm{deg}\ge 2$ has all neighbors pairwise friends. In a clique of size $k\ge 3$, we CANNOT operate because all pairs are already friends. So we must argue more carefully that terminal states are matchings.

Step 5 (Revised — Component analysis): At termination, each component is a clique. Suppose a terminal clique has size $k\ge 3$. Consider the graph invariant: for each vertex $v$, $(-1{)}^{\mathrm{deg}(v)}$ — the product ${\prod }_v(-1{)}^{\mathrm{deg}(v)}=(-1{)}^{\sum \mathrm{deg}(v)}=(-1{)}^{2|E|}=1$ is invariant. Also, each operation preserves the parity of each individual vertex's degree modulo 2 (since $\mathrm{deg}(A)$ changes by $-2$, $\mathrm{deg}(B)$ and $\mathrm{deg}(C)$ are unchanged). So the parity of each vertex's degree is invariant!

Initially: 1010 users have odd degree (1009) and 1009 users have even degree (1010). In a terminal clique of size $k$, each member has degree $k-1$. The vertices that initially had odd degree must still have odd degree, so $k-1$ is odd, i.e., $k$ is even. Similarly for even-degree vertices. Since we have 1010 odd-parity vertices and 1009 even-parity vertices, and cliques must be uniform in parity, the odd-parity vertices form cliques of even size and even-parity vertices form cliques of odd size. The only even clique size with odd degree per vertex is $k=2$, and the only odd clique size with even degree per vertex is $k=1$. So terminal state has the 1010 odd-parity vertices in 505 pairs (edges) and 1009 even-parity vertices as isolates.

This is a matching with 505 edges and every vertex has degree $\le 1$. $■$