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.

Official text of the problem. Official problem paper (PDF)

Solution

Represent the network by a simple undirected graph, with users as vertices and friendships as edges. An allowed operation replaces edges \(ab,ac\) by the edge \(bc\), provided \(bc\) is absent. It decreases the degree of \(a\) by two and leaves all other degrees unchanged. Thus every degree keeps its parity, while the number of edges decreases by one.

We prove the following stronger statement.

Lemma. Every finite connected graph that is not complete and has a vertex of odd degree can be transformed by allowed operations into a graph whose vertices all have degree at most one.

A bridge is an edge whose deletion disconnects its connected component.

First, we can obtain a connected graph containing a bridge. Suppose the current graph has no bridge. Choose a vertex \(v\) of maximum degree \(d\). An odd-degree vertex cannot have degree one, since its incident edge would be a bridge. Therefore \(d\geq 3\).

The neighbours of \(v\) cannot all be pairwise adjacent. Indeed, if they were, each of them would already have \(d\) neighbours within the set consisting of \(v\) and its neighbours. By maximality of \(d\), none would have a neighbour outside this set. Connectedness would then imply that the whole graph was complete.

We now choose an operation that preserves connectedness.

  • If deleting \(v\) leaves a connected graph, choose two nonadjacent neighbours \(a,b\) of \(v\) and replace \(va,vb\) by \(ab\). The graph without \(v\) remains connected, and \(v\) retains \(d-2\geq 1\) neighbours, so the resulting graph is connected.
  • If deleting \(v\) leaves several components, each contains at least two neighbours of \(v\): otherwise its unique edge to \(v\) would be a bridge. Choose neighbours \(a,b\) in different components. They are nonadjacent, so the operation at \(v\) is allowed. After it, every component of the graph without \(v\) still has a neighbour of \(v\), so connectedness is again preserved.

The resulting graph is not complete, since \(va\) is now absent, and it still has an odd-degree vertex by parity preservation. Consequently, whenever there is no bridge, we can repeat this procedure. Since each operation decreases the number of edges, the procedure must eventually produce a bridge.

Second, any graph in which every component with at least two vertices contains a bridge can be reduced to the required form. We show how to preserve this property while reducing any component \(H\) with at least three vertices.

Choose a bridge \(uv\) of \(H\). At least one endpoint, say \(v\), has degree at least two; otherwise connectedness would force \(H\) to consist of just this edge.

If \(v\) has an incident edge \(vw\) that is not a bridge, choose such an edge. Otherwise, choose any neighbour \(w\neq u\). In either case, \(u\) and \(w\) are nonadjacent, since an edge \(uw\) would put the bridge \(uv\) in a triangle. Hence we may replace \(uv,vw\) by \(uw\).

There are two cases.

  • The edge \(vw\) is not a bridge. The two components of \(H-uv\) remain connected after \(vw\) is deleted: if the component containing \(v,w\) became disconnected, then \(H-vw\) would also be disconnected, contrary to the choice of \(vw\). The new edge \(uw\) joins these two components and is a bridge. Thus the resulting graph is connected and contains a bridge.
  • Every edge incident with \(v\) is a bridge. Deleting \(uv\) and \(vw\) produces three components, containing \(u,v,w\), respectively. The new edge \(uw\) joins the first and third components and is a bridge. The component containing \(v\) is either the isolated vertex \(v\), or contains a remaining edge incident with \(v\). Such an edge is still a bridge, because deleting other edges cannot create a path bypassing it.

Thus every resulting component with at least two vertices still contains a bridge. We can repeat whenever some component has at least three vertices. The number of edges decreases each time, so eventually every component has at most two vertices. This proves the lemma.

We now apply it to the given network. Every vertex initially has degree at least \(1009\), so every connected component has at least \(1010\) vertices. Two components would therefore require at least \(2020\) vertices. Since there are only \(2019\), the graph is connected.

It is not complete, because its degrees are at most \(1010<2018\), and it has vertices of odd degree \(1009\). The lemma therefore supplies a sequence of allowed events after which every vertex has degree at most one, as required. \(\square\)

The solution was checked against the official IMO shortlist solutions.