(50分)给定空间中 $10$ 个点,其中任意四点不在一个平面上.将某些点之间用线段相连,若得到的图形中没有三角形也没有空间四边形,试确定所连线段数目的最大值.
【难度】
【出处】
【标注】
【答案】
以这 $10$ 个点为顶点,所连线段为边,得到一个 $10$ 阶简单图 $G$.我们证明 $G$ 的边数不超过 $15$.设 $G$ 的顶点为 $v_{1},v_{2},\cdots,v_{10}$,共有 $k$ 条边,用 $\deg(v_{i})$ 表示顶点 $v_{i}$ 的度,若 $\deg(v_{i})\leqslant 3$ 对 $i=1,2,\cdots,10$ 都成立,则\[k=\dfrac{1}{2}\sum\limits_{i=1}^{10}\deg(v_{i})\leqslant \dfrac{1}{2}\cdot 10\cdot 3=15.\]假设存在 $v_{i}$ 满足 $\deg(v_{i})\geqslant 4$.不妨设 $\deg(v_{1})=n\geqslant 4$,且 $v_{1}$ 与 $v_{2},\cdots,v_{n+1}$ 均相邻.于是 $v_{2},\cdots,v_{n+1}$ 之间没有边,否则就形成三角形.所以 $v_{1},v_{2},\cdots,v_{n+1}$ 之间恰有 $n$ 条边.
对每个 $j(n+2\leqslant j\leqslant 10)$,$v_{j}$ 至多与 $v_{2},v_{3},\cdots,v_{n+1}$ 中的一个顶点相邻(否则设 $v_{j}$ 与 $v_{s},v_{t},2\leqslant s<t\leqslant n+1$ 相邻,则 $v_{1},v_{s},v_{j},v_{t}$ 就对应了一个空间四边形的四个顶点,这与题设条件矛盾.),从而 $v_{2},\cdots, v_{n+1}$ 与 $v_{n+2},\cdots,v_{10}$ 之间的边数至多 $10-(n+1)=9-n$ 条.
在 $v_{n+2},\cdots,v_{10}$ 这 $9-n$ 个顶点之间,由于没有三角形,由托兰定理,至多 $\left[\dfrac{(9-n)^{2}}{4}\right]$ 条边.因此 $G$ 的边数\[\begin{split}k&\leqslant n+(9-n)+\left[\dfrac{(9-n)^{2}}{4}\right]\\&=9+\left[\dfrac{(9-n)^{2}}{4}\right]\\&\leqslant 9+\left[\dfrac{25}{4}\right]=15.\end{split}\]如图给出的图形共有 $15$ 条边,且满足要求.综上所述,所求边数的最大值为 $15$.
【解析】
答案 解析 备注
0.118320s