第2题

设

n\ge3

，圆上有

E

个互异点组成集合

2n-1

。其中恰有

k

个点染黑。若存在一对黑点，使其中一条弧的内部恰含

n

中

E

个点，则称染色良好。求使任意

k

点染色都良好的最小

k

。

第 3/4 步：用独立数限制黑点数

\alpha(C_{2n-1})=n-1,\qquad \alpha\left(3C_{(2n-1)/3}\right)=n-2

详细分析

没有良好点对的染色是图中的独立集。长度为 L 的奇圈独立数为 (L-1)/2。因此单圈时黑点至多 n-1 个；三圈时总最大数为三倍的 ((2n-1)/3-1)/2，即 n-2。