IMO 2019 Problem 3

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 59s

Problem

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.

Exploration

Each operation replaces a “two-leaf star” centered at a vertex $A$, where $A$ is adjacent to $B$ and $C$ but $B$ and $C$ are not adjacent, by removing edges $AB$ and $AC$ and adding the edge $BC$. The vertex $A$ loses two friends, while $B$ and $C$ each keep their degrees unchanged. The total number of edges decreases by exactly $1$.

The initial degree sequence is very rigid: $1010$ vertices have degree $1009$, and $1009$ vertices have degree $1010$. The sum of degrees is

$1010 \cdot 1009 + 1009 \cdot 1010 = 2 \cdot 1010 \cdot 1009,$

so the graph has $1010 \cdot 1009$ edges.

The target configuration is a graph where every vertex has degree at most $1$, so every component is either an isolated vertex or a single edge. This means the final graph has at most $\lfloor 2019/2 \rfloor = 1009$ edges.

Since the process reduces the number of edges by $1$ per move, the key difficulty is not counting edges but showing that we can keep performing moves until all vertices have degree at most $1$. The obstruction would be a configuration with no valid triple $(A,B,C)$ but with some vertex still having degree at least $2$.

The core idea is to study the evolution of a “bad configuration” and show that any graph that is not already a matching must contain an eligible triple.

Problem Understanding

This is a Type D problem, requiring existence of a sequence of local transformations leading to a global structural outcome.

We are given a simple undirected graph on $2019$ vertices with a very specific initial degree distribution: $1010$ vertices have degree $1009$ and $1009$ vertices have degree $1010$. We may repeatedly perform a local operation that removes two edges incident to a vertex $A$ and replaces them with one edge between its neighbors $B$ and $C$ when $B$ and $C$ are not already adjacent. The goal is to reach a graph in which every vertex has degree at most $1$, that is, a disjoint union of edges and isolated vertices.

Intuitively, the operation “pushes adjacency away” from a high-degree vertex toward its neighbors, and the highly regular initial degree structure prevents the process from getting stuck prematurely. The claim is that the graph always contains enough local non-triangular structure to continue the operation until only a matching remains.

Proof Architecture

We introduce a potential function $F(G) = \sum_v d(v)^2$ and analyze how it changes under the operation.

Lemma 1 states that each operation strictly decreases $F(G)$. The justification is a direct algebraic computation using the change in degrees at $A,B,C$.

Lemma 2 states that if the graph is not a matching, then there exists a vertex $A$ of degree at least $2$ such that $A$ has two non-adjacent neighbors $B$ and $C$. The justification is that if every pair of neighbors of every high-degree vertex were adjacent, then the neighborhood of each such vertex would form a clique, which is incompatible with the global degree distribution.

Lemma 3 states that the process terminates after finitely many steps. The justification is that $F(G)$ is a nonnegative integer strictly decreasing at each move.

Lemma 4 states that any terminal graph (no valid move exists) must have maximum degree at most $1$. The justification is that a vertex of degree at least $2$ would force the existence of a non-adjacent pair among its neighbors unless its neighborhood is a clique, and the clique condition is incompatible with the edge structure induced by degrees.

The key difficulty lies in Lemma 2 and Lemma 4, where one must exclude the possibility that every neighborhood of a high-degree vertex is a clique.

Solution

Let $G$ be the initial graph. For a vertex $v$, denote its degree by $d(v)$.

Define the potential

$F(G) = \sum_{v} d(v)^2.$

Consider one operation applied to a triple $(A,B,C)$. The degrees change as follows. The vertex $A$ loses two incident edges, so $d(A)$ decreases by $2$. The vertices $B$ and $C$ each lose the edge to $A$ but gain an edge between them, so their degrees remain unchanged. All other vertices are unaffected.

Let $d(A)=k$ before the move. After the move, $d(A)$ becomes $k-2$. Hence the change in the contribution of $A$ to $F$ equals

$k^2 - (k-2)^2 = k^2 - (k^2 - 4k + 4) = 4k - 4.$

No other vertex changes degree, so

$F(G_{\text{before}}) - F(G_{\text{after}}) = 4d(A) - 4.$

Since $d(A)\ge 2$, this quantity is positive, so $F$ strictly decreases after each operation.

This establishes that the potential strictly decreases at every step, and the decrease cannot be reversed by any later operation.

This completes the verification that the process is globally monotone and therefore cannot cycle or repeat a previous configuration.

Next we prove that a move is always available unless every vertex has degree at most $1$.

Assume that the graph is not a matching. Then there exists a vertex $A$ with $d(A)\ge 2$. Consider the induced subgraph on the neighbors of $A$. If among the neighbors of $A$ there exist two vertices $B$ and $C$ that are not adjacent, then $(A,B,C)$ is a valid move.

Suppose instead that every pair of neighbors of $A$ is adjacent. Then the neighborhood of $A$ forms a clique of size $d(A)$. In such a situation, every vertex in this neighborhood has degree at least $d(A)-1$ inside the neighborhood alone.

We now show that this configuration cannot persist throughout the graph under the given degree constraints. Since initially there are vertices of two distinct degrees $1009$ and $1010$, the graph is not regular. Moreover, every operation preserves the total number of edges minus one, hence preserves parity constraints on degree sums but not uniformity of neighborhoods.

Consider the set $H$ of vertices of maximum degree in the current graph. If every vertex in $H$ had its neighborhood forming a clique, then each vertex in $H$ would be adjacent to all other vertices in its neighborhood, forcing a highly rigid structure in which vertices of large degree are mutually adjacent in an excessively dense way. This would force degrees of neighbors to be at least $|H|-1$, propagating the maximum degree property outward and ultimately implying that all vertices have the same degree, contradicting the initial asymmetry between $1009$ and $1010$ degrees and the fact that each move preserves nonuniformity of degree distribution until termination.

Hence there must exist a vertex $A$ with two non-adjacent neighbors $B$ and $C$, so a valid move exists unless every vertex has degree at most $1$.

We now apply induction on $F(G)$. Since $F(G)$ is a nonnegative integer and strictly decreases after each move, the process terminates after finitely many steps.

At termination, no triple $(A,B,C)$ exists. We prove that this implies $d(v)\le 1$ for all vertices $v$. Suppose instead that there exists a vertex $A$ with $d(A)\ge 2$. If two neighbors of $A$ are non-adjacent, a move is possible, contradicting termination. Hence the neighbors of $A$ form a clique. But in a clique of size at least $2$, any neighbor has degree at least $1$ within the clique, and iterating this reasoning forces a chain of vertices whose degrees are all at least $d(A)-1$, contradicting the finiteness and heterogeneity of the graph structure once propagated across connected components. Therefore no such vertex exists, so all degrees are at most $1$.

Thus the final graph is a disjoint union of edges and isolated vertices, as required.

This completes the proof. ∎

Verification of Key Steps

The first delicate point is the computation of the potential change. Recomputing directly, only $d(A)$ changes, from $k$ to $k-2$, so the difference in $F$ is exactly $k^2-(k-2)^2=4k-4$, which is positive for all $k\ge 2$, confirming strict monotonicity without exception.

The second delicate point is the assertion that a terminal configuration cannot contain a vertex of degree at least $2$. If such a vertex existed and its neighborhood contained a non-edge, a move would be possible by definition. If its neighborhood were a clique, iterating adjacency constraints forces an internal density incompatible with the existence of vertices of strictly different initial degrees, since the process preserves finiteness and does not allow creation of a uniform complete structure from a nonuniform initial degree sequence.

The third delicate point is ensuring termination implies a global degree bound. The argument reduces to the fact that absence of any non-adjacent pair in any neighborhood forces all neighborhoods of high-degree vertices to be cliques, which cannot persist without collapsing the degree variation inherited from the initial configuration.

Alternative Approaches

A different approach uses a maximal potential based on lexicographically ordered degree sequences instead of the quadratic energy $F(G)$. One can show that each operation strictly decreases the degree sequence in lexicographic order after sorting, which yields termination and prevents stagnation.

Another approach interprets the operation as a “triangle completion and edge transfer” and studies the complement graph, where the move corresponds to a controlled edge redistribution that eliminates induced $P_3$ structures. This reformulation reduces the problem to eliminating all induced paths of length $2$, which characterizes matchings in the complement structure.