MathLabs

第3题

一个社交网络有 20192019 名用户，其中一些用户成对为朋友（朋友关系是对称的）。以下事件可以反复发生，每次一个：三名用户 AA、BB、CC 满足 AA 同时与 BB 和 CC 是朋友，但 BB 与 CC 不是朋友；改变他们的朋友关系，使得 BB 与 CC 现在成为朋友，但 AA 不再与 BB 是朋友，也不再与 CC 是朋友。其他所有朋友关系保持不变。最初，10101010 名用户各有 10091009 个朋友，10091009 名用户各有 10101010 个朋友。证明存在一系列这样的事件，使得之后每名用户至多与另一名用户是朋友。
第 5/6 步：在树中切换而不产生圈
上一步下一步
T a tree,AB,AC∈E(T), BC∉E(T)⟹ T′=(T∖{AB,AC})∪{BC} is a forestT\text{ a tree},\quad AB,AC\in E(T),\ BC\notin E(T)\Longrightarrow\ T'=(T\setminus\{AB,AC\})\cup\{BC\}\text{ is a forest}
详细分析

现在令 TT 为上面得到的生成树。当顶点 AA 有两个邻点 B,CB,C 时，从 BB 到 CC 的唯一道路是 B−A−CB-A-C，所以 BB 与 CC 不相邻，切换合法。从树中删除 ABAB 与 ACAC 后它分成三个连通分支，再加入 BCBC 将含有 BB 和 CC 的两个分支连接起来；因此所得图是一个森林（边数少一条），不会产生圈。同样的论证适用于之后得到的每个森林。