2008 年辽宁预赛 · 第 12 题

解答

任意三点不共线，否则再取一点便有四点共面。因此三角形与图中的三点完全子图一一对应，四面体也恰对应四点完全子图。以下证明九点无四点完全子图的图至多有二十七个三角形。 在全部这类图中，先取三角形数最多者，再取其中边数最多者，再取其中 $\sum d(v{)}^2$ 最大者。若两点 $u,v$ 不相邻，把 $u$ 的邻点改为与 $v$ 完全相同，称为将 $u$ 克隆为 $v$。它不产生四点完全子图：若新四点完全子图含 $u$，将 $u$ 换成 $v$ 就是旧图中的一个。 记 $t(w)$ 为经过点 $w$ 的三角形数。克隆使三角形总数增加 $t(v)-t(u)$，所以极值图中任何不相邻两点的 $t$ 必相等。再比较边数，同理它们的度也相等。 若其邻点集合仍不同，记 $U=N(u)\setminus N(v),V=N(v)\setminus N(u)$，两集合大小相同为 $r>0$。克隆一个方向使 $V$ 中点的度加一、$U$ 中点的度减一；反向克隆交换二者。两个方向的平方度和增量相加为 $4r>0$，必有一个方向增加平方度和，同时前两极值不变，矛盾。因此不相邻点具有完全相同的邻点集合。 这说明不相邻关系连同自身形成等价类：若 $u,v$ 不相邻且 $v,w$ 不相邻，邻点相同便迫 $u,w$ 不相邻。每类内部无边、异类之间全有边，故图为完全多部图。禁止四点完全子图使非空类最多三个，记大小为 $a,b,c$（不足三个时补零），和为九。三角形数为 $abc\le ((a+b+c)/3{)}^3=27$。 把九点分成三组，每组三点，只连接不同组的点，便有 $3\cdot 3\cdot 3=27$ 个三角形且没有四面体。所以所求最大值为 $\boxed{27}$。