给定空间中 $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_{i=1}^{10} deg(v_i)\leqslant \dfrac{1}{2}\dot10\dot3=15$.假设存在 $v_i$ 满足 $deg(v_i)\geqslant 4$.不妨设 $deg(v_i)=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_n$ 这 $9-n$ 个顶点之间,由于没有三角形,由托兰定理,至多 $[\dfrac{(9-n)^2}{4}]$ 条边.因此 $G$ 的边数 $k\leqslant n+(9-n)+[\dfrac{(9-n)^2}{4}]=9+[\dfrac{(9-n)^2}{4}]\leqslant 9+[\dfrac{25}{4}]=15$.
如图给出的图共有15条边,且满足要求.综上所述,所求边数的最大值为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_{i=1}^{10} deg(v_i)\leqslant \dfrac{1}{2}\dot10\dot3=15$.假设存在 $v_i$ 满足 $deg(v_i)\geqslant 4$.不妨设 $deg(v_i)=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_n$ 这 $9-n$ 个顶点之间,由于没有三角形,由托兰定理,至多 $[\dfrac{(9-n)^2}{4}]$ 条边.因此 $G$ 的边数 $k\leqslant n+(9-n)+[\dfrac{(9-n)^2}{4}]=9+[\dfrac{(9-n)^2}{4}]\leqslant 9+[\dfrac{25}{4}]=15$.

答案
解析
备注