2012 年安徽预赛 · 第 12 题

解答

建立一个有 $n$ 个顶点的图：顶点 $i,j$ 之间连边，当且仅当 ${\mathbf{a}}_i\cdot {\mathbf{a}}_j<0$。边数即为 $M$；零向量对应孤立点。

先说明图中不存在四个两两相连的顶点。否则这四个向量均非零，将它们的方向按圆周顺序排列。四个相邻方向间隔之和为 $2\pi$，至少有一个间隔不超过 $\pi /2$，这两个向量的数量积非负，与连边条件矛盾。

需要一个辅助结论：若一个无三角形的图有 $q$ 个顶点、$e$ 条边，则 $e\le q^2/4$。记各顶点度数为 $d_i$。每条边两端不能有公共邻点，故两端度数之和不超过 $q$。对全部边求和，得到

若 $q=0$ 或 $e=0$，结论显然；否则由柯西不等式，

所以 $e\le q^2/4$。

现在取原图最大度数为 $d$ 的顶点 $v$。若 $d=0$，则 $M=0$。否则其邻点集 $N$ 有 $d$ 个顶点，$N$ 内不可能有三角形，否则加上 $v$ 就得到四个两两相连的顶点。因此 $N$ 内边数不超过 $d^2/4$。

记 $C$ 为其余 $n-d$ 个顶点的集合。跨越 $N,C$ 的边加上 $C$ 内部的边，不超过 $C$ 中所有顶点的度数之和；后者至多为 $(n-d)d$。于是