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 3 of 6: A connected graph that is not a clique, cycle, or tree admits a safe toggle

Previous step Next step

G\ \text{connected},\ G\neq K_{|V|},\ G\neq C_{|V|},\ G\ \text{not a tree}\ \Longrightarrow\ \exists\, A,B,C:\ G'\ \text{connected}

Detailed analysis

Suppose $G$ is connected but is none of a clique, a cycle, or a tree; then $G$ contains a cycle but is not itself that cycle. Take a shortest cycle $C_0$ . If $G$ has no triangle, pick a vertex $b$ outside $C_0$ adjacent to some $a$ on $C_0$ (it exists since $G$ is connected and larger than $C_0$ ), and let $c$ be a neighbor of $a$ on $C_0$ ; minimality of $C_0$ forces $b$ and $c$ to be non-adjacent, so toggling $a,b,c$ is legal, and it keeps the graph connected because $a$ keeps its other cycle-neighbor while $b$ reconnects through its new edge to $c$ . If instead $G$ has a triangle, take a maximal clique $K$ (a proper subset of the vertices) and an edge from a vertex $a\in K$ to some $b\notin K$ ; maximality gives a vertex $c\in K$ not adjacent to $b$ , and toggling $a,b,c$ is legal and keeps the graph connected, because $a$ stays linked to the rest of $K$ while $b$ reconnects through $c$ .