第3题

一个社交网络有

2019

名用户，其中一些用户成对为朋友（朋友关系是对称的）。以下事件可以反复发生，每次一个：三名用户

A

、

B

、

C

满足

A

同时与

B

和

C

是朋友，但

B

与

C

不是朋友；改变他们的朋友关系，使得

B

与

C

现在成为朋友，但

A

不再与

B

是朋友，也不再与

C

是朋友。其他所有朋友关系保持不变。最初，

1010

名用户各有

1009

个朋友，

1009

名用户各有

1010

个朋友。证明存在一系列这样的事件，使得之后每名用户至多与另一名用户是朋友。

第 4/6 步：初始网络连通、非完全图，且永远不会变成圈

上一步下一步

1009+1009+2>2019,\qquad \deg(A_0)=1009\ (\text{odd, invariant under toggles})\ \Longrightarrow\ G\ \text{never becomes a cycle}

详细分析

每名用户的度数为 $1009$ 或 $1010$ ，因此任意两个不相邻用户的邻居数之和至少为 $1009+1009>2019-2$ ，由鸽笼原理知他们必有公共邻居；因此初始图 $G$ 连通。它不是完全图，因为 $2019$ 个顶点上的完全图需要度数 $2018$ 。由第 2 步，每次切换只有一个顶点的度数发生变化，且只变化 $2$ ，所以每个顶点度数的奇偶性永远固定；一个以奇数度 $1009$ 开始的顶点永远无法达到圈所要求的偶数度 $2$ ，所以 $G$ 永远不会变成一个圈。由第 3 步，只要 $G$ 保持连通且尚未成为树，我们就可以继续对其切换，而每次这样的切换都会严格减少边数，因此这个过程必须停止：它恰好在图变为覆盖全部 $2019$ 个顶点的一棵生成树时停止。