IMO 2019 Problem 3

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.

Proposed by Adrian Beker, Croatia

The official solutions are much more elegant.

====================================

Proof:

Consider the graph of friendship $G$. Each operation reduces the number of edge by $1$, so it suffices to show that we can go on till the end condition is met without ever creating any isolated clique with more than $2$ vertices. Note that no vertex's degree will ever change parity.

Terminology

Let $C$ and $D$ be the induced subgraphs of $G$ with vertex sets being those with odd and even degrees in $G$, respectively.

An almost-clique is obtained by removing an edge from a clique. By induction it could be proved that within it the end condition is achievable.

We define three types of operation: intra operation applies within $C$ or $D$; cross operation removes an edge from $C$ or $D$, removes one and adds another to between $C$ and $D$; scissor operation removes $2$ edges between $C$ and $D$. Each operation belongs to one of them.

When $G$ has an isolated clique with more than $2$ vertices, it is in dead state because we could not touch that clique anymore.

Remark An isolated clique is either within $C$ or $D$ because of parity of vertex degree.

Algorithm

Initially, $G$ is not in dead state.

While end condition is not met

  If intra operation can be applied

    Do so

  Else if cross operation can be applied

    Do so

  Else

    Apply scissor operation

Scissor operation is never applied, because cross operation is always possible in that situation. Cross operation doesn't cause $G$ to be in dead state, and it creates an almost-clique $X$ in $C$ or $D$. We can then apply intra operation on $X$ until the end condition holds within $X$. Then, we are forced to apply cross operation again, and so on. So we have the following.

Lemma Once a cross operation has been performed, the end goal is achievable.

It remains to show that we can keep $G$ away from dead state before the first cross operation, i.e. there exists a sequence of first consecutive intra operations that do not lead to dead state. Note that each vertex in $D$ initially has degree $1010>1008=|D|-1$, so is connected to $C$. In other words, we only have to make sure no isolated clique with more than $2$ vertices shows up when applying first intra operations to $C$.

We only discuss one case out of three, and the other two are similar. Suppose an intra operation connects vertices $b$ and $c$ and disconnects them from $a$, and we end up with isolated cliques $E$ and $F$, both of even size since they are in $C$. Then we could have produce almost-cliques $E'$ and $F'$, where $a$ and $d$ in $E'$ are disconnected, $b$ and $c$ in $F'$ are disconnected, $a$ connects with $c$, and $b$ connects with $d$. Then by operations inside $E'$ and $F'$ the end goal is achieved for all vertices within.

Q.E.D.