第3题

一个社交网络有

2019

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

A

、

B

、

C

满足

A

同时与

B

和

C

是朋友，但

B

与

C

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

B

与

C

现在成为朋友，但

A

不再与

B

是朋友，也不再与

C

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

1010

名用户各有

1009

个朋友，

1009

名用户各有

1010

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

第 6/6 步：在匹配处终止

|E_{t+1}|=|E_t|-1,\qquad \text{no legal toggle}\Longleftrightarrow\ \deg(v)\le 1\quad\text{for every }v

详细分析

在当前森林中继续任意进行合法切换。每次切换都使边数减少 $1$ ，所以有限过程必定终止。终止时，若某个顶点 $A$ 有两个邻点 $B,C$ ，无圈性将推出 $BC$ 不存在，从而还能进行一次合法切换；因此每个顶点的度数至多为 $1$ 。所以最终的朋友图是一个匹配加上一些孤立顶点，正是所要求的结果。