在有八个顶点的简单图中，没有四边形的图的边数的最大值是多少？（简单图是指任一点与自己没有边相连，而且任 何两个点之间如果有边相连，就只有一条边相连的图）
【难度】
【出处】
1992第7届CMO试题
【标注】
【答案】
略
【解析】
下图是有八个顶点，十一条边的简单图，其中没有四边形．
下面证 $ 11$ 即是所要求的最大值．为此，只要证明有十二条边的图中必有四边形．先指出几个事实：
（1）设点 $A$ 与点 $A_{1}, A_{2}, \cdots, A_{k}$ 都有边相连，又 $B$ 是与 $A$ 不同的顶点（$B$ 可以是 $\left\{A_{1}, A_{2}, \cdots, A_{k}\right\}$ 中点），如果 $B$ 与 $\left\{A_{1}, A_{2}, \cdots, A_{k}\right\}$ 中的两个点有边相连，则图中有四边形．
（2）四个顶点的图中如果有五条边，就必定有四边形．
设 $G$ 是有八个顶点，十二条边的简单图，下证 $G$ 必有四边形．用反证法，即设 $G$ 没有四边形．用 $d_{1}, d_{2}, \cdots, d_{8}$ 表示 $G$ 的八个顶点 的度数，由于 $\displaystyle \sum\limits_{i=1}^{8} d_{i}=2 \times 12=24, \max \left(d_{1}, d_{2}, \cdots, d_{3}\right) \geqslant 3$ 以下分三种情况讨论．
（i）$\max \left(d_{1}, d_{2}, \cdots, d_{8}\right)=3$．这时，$G$ 的每一个顶点的度数都是 $3$．任 取一个顶点 $A$，与 $A$ 有边相连的顶点设为 $A_{1}, A_{2}, A_{3}$，其余四个顶点为 $B_{1}, B_{2}, B_{3}, B_{4}$．由（1），$\left\{B_{1}, B_{2}, B_{3}, B_{4}\right\}$ 中点与 $\left\{A_{1}, A_{2}, A_{3}\right\}$ 中点相连的边至多只有四条．而 $\left\{A_{1}, A_{2}, A_{3}\right\}$ 中点相连的边至多只有一条，所以，在 $\left\{B_{1}, B_{2}, B_{3}, B_{4}\right\}$ 这些点中相连的边至少有 $12 - 3 -4 - 1 = 4$ 条（由（2）可知也只有四条）．我们只考虑这四个顶点及联结它们的四条边．这时，其中必有某一顶点的度数是 $1$（如这四个点度数都是 $2$，就成为一个四边形）．从而有顶点度数为 $3$，即 $\left\{B_{1}, B_{2}, B_{3}, B_{4}\right\}$ 中必有一点（不妨设为 $B_1$，）与其他三点 $B_{2}, B_{3}, B_{4}$ 都有边相连．而 $\left\{B_{1}, B_{2}, B_{3}, B_{4}\right\}$ 中的点与 $\left\{A_{2}, A_{3}, A_{4}\right\}$ 中的点相连的边数为4，$B_1$ 必与 $\left\{A_{2}, A_{3}, A_{4}\right\}$ 中某一点有边相连．这样，在图 $G$ 中，$ B_1 $ 的度数将是 $ 4$，与假设矛盾．
（ii）$\max \left(d_{1}, \cdots, d_{8}\right)=4$．取一个度数为 $4$ 的顶点 $ A$，设与 $A$ 有边相连的顶点为 $A_{1}, A_{2}, A_{3}, A_{4}$，其余三个顶点为 $B_{1}, B_{2}, B_{3}$．由（1）$\left\{A_{1}, A_{2}, A_{3}, A_{4}\right\}$ 中的点相连的边至多是 $2$ 条，将 $\left\{B_{1}, B_{2}, B_{3}\right\}$ 中点与 $\left\{A_{1}, A_{2}, A_{3}, A_{4}\right\}$ 中点相连的边至多是3条，而 $\left\{B_{1}, B_{2}, B_{3}\right\}$ 中的点相连的边显然至多是 $3$ 条由于总的边数是 $12$ 条，因此上 述的各种边数恰为 $2,3,3$．于是，$\left\{A_{1}, A_{2}, A_{3}, A_{4}\right\}$ 中点相连的边有 $2$ 条，不妨设为 $A_{1} A_{2}$ 及 $A_{3} A_{4}$（这两条边不会有公共顶点，否则将出现四边形）．$\left\{B_{1}, B_{2}, B_{3}\right\}$ 中每一点都与 $\left\{A_{1}, A_{2}, A_{3}, A_{4}\right\}$ 中某一点 有边相连，$B_{1} B_{2}, B_{1} B_{3}, B_{2} B_{3}$ 都是 $G$ 中的边．由于 $\left\{B_{1}, B_{2}, B_{3} \right\}$ 都与 $\{ A_{1}, A_{2}, A_{3}, A_{4} \}$ 中某一点相连，因此至少有两个点与 $\left\{A_{1}, A_{2}\right\}$ 或 $\left\{A_{3}, A_{4}\right\}$ 中某一点相连，不妨设 $\left\{B_{1}, B_{2}, B_{3}\right\}$ 中有两点 $B_{1}, B_{2}$ 与 $\left\{A_{1}, A_{2} \right\}$ 中点有边相连这时，如果 $B_{1}, B_{2}$ 与 $\left\{A_{1}, A_{2}\right\}$ 中不同的点分别有边相连，则因为 $A_{1} A_{2}, B_{1} B_{2}$ 都是边，仍有四边形，与假设矛盾．
（iii）$\max \left(d_{1}, \cdots, d_{8}\right)>4$．取一个度数最大的顶点 $ A$，与 $A$ 有边 相连的顶点集记为 $S$，其余顶点集记为 $T$．$|S|=\max \left(d_{1}, \cdots, d_{8}\right)$ $T$ 中的点与 $S$ 中的点相连的边数至多有 $|T|$ 条，$T$ 中点相连的边数至多有 $\mathrm{C}_{|T|}^{2}$ 条，$S$ 中点相连的边至多有 $\left[\dfrac{|S|}{2}\right]$ 条这样，图中的
边数不超过 $|S|+|T|+C_{|r|}^{2}+\left[\dfrac{|S|}{2}\right]=7+C_{|r|}^{2}+\left[\dfrac{|S|}{2}\right]$ 当 $|S|=5,6,7$ 时，都不可能使边数为 $12$．综上所述，即知所求的最大值为 $11$．
下面证 $ 11$ 即是所要求的最大值．为此，只要证明有十二条边的图中必有四边形．先指出几个事实：（1）设点 $A$ 与点 $A_{1}, A_{2}, \cdots, A_{k}$ 都有边相连，又 $B$ 是与 $A$ 不同的顶点（$B$ 可以是 $\left\{A_{1}, A_{2}, \cdots, A_{k}\right\}$ 中点），如果 $B$ 与 $\left\{A_{1}, A_{2}, \cdots, A_{k}\right\}$ 中的两个点有边相连，则图中有四边形．
（2）四个顶点的图中如果有五条边，就必定有四边形．
设 $G$ 是有八个顶点，十二条边的简单图，下证 $G$ 必有四边形．用反证法，即设 $G$ 没有四边形．用 $d_{1}, d_{2}, \cdots, d_{8}$ 表示 $G$ 的八个顶点 的度数，由于 $\displaystyle \sum\limits_{i=1}^{8} d_{i}=2 \times 12=24, \max \left(d_{1}, d_{2}, \cdots, d_{3}\right) \geqslant 3$ 以下分三种情况讨论．
（i）$\max \left(d_{1}, d_{2}, \cdots, d_{8}\right)=3$．这时，$G$ 的每一个顶点的度数都是 $3$．任 取一个顶点 $A$，与 $A$ 有边相连的顶点设为 $A_{1}, A_{2}, A_{3}$，其余四个顶点为 $B_{1}, B_{2}, B_{3}, B_{4}$．由（1），$\left\{B_{1}, B_{2}, B_{3}, B_{4}\right\}$ 中点与 $\left\{A_{1}, A_{2}, A_{3}\right\}$ 中点相连的边至多只有四条．而 $\left\{A_{1}, A_{2}, A_{3}\right\}$ 中点相连的边至多只有一条，所以，在 $\left\{B_{1}, B_{2}, B_{3}, B_{4}\right\}$ 这些点中相连的边至少有 $12 - 3 -4 - 1 = 4$ 条（由（2）可知也只有四条）．我们只考虑这四个顶点及联结它们的四条边．这时，其中必有某一顶点的度数是 $1$（如这四个点度数都是 $2$，就成为一个四边形）．从而有顶点度数为 $3$，即 $\left\{B_{1}, B_{2}, B_{3}, B_{4}\right\}$ 中必有一点（不妨设为 $B_1$，）与其他三点 $B_{2}, B_{3}, B_{4}$ 都有边相连．而 $\left\{B_{1}, B_{2}, B_{3}, B_{4}\right\}$ 中的点与 $\left\{A_{2}, A_{3}, A_{4}\right\}$ 中的点相连的边数为4，$B_1$ 必与 $\left\{A_{2}, A_{3}, A_{4}\right\}$ 中某一点有边相连．这样，在图 $G$ 中，$ B_1 $ 的度数将是 $ 4$，与假设矛盾．
（ii）$\max \left(d_{1}, \cdots, d_{8}\right)=4$．取一个度数为 $4$ 的顶点 $ A$，设与 $A$ 有边相连的顶点为 $A_{1}, A_{2}, A_{3}, A_{4}$，其余三个顶点为 $B_{1}, B_{2}, B_{3}$．由（1）$\left\{A_{1}, A_{2}, A_{3}, A_{4}\right\}$ 中的点相连的边至多是 $2$ 条，将 $\left\{B_{1}, B_{2}, B_{3}\right\}$ 中点与 $\left\{A_{1}, A_{2}, A_{3}, A_{4}\right\}$ 中点相连的边至多是3条，而 $\left\{B_{1}, B_{2}, B_{3}\right\}$ 中的点相连的边显然至多是 $3$ 条由于总的边数是 $12$ 条，因此上 述的各种边数恰为 $2,3,3$．于是，$\left\{A_{1}, A_{2}, A_{3}, A_{4}\right\}$ 中点相连的边有 $2$ 条，不妨设为 $A_{1} A_{2}$ 及 $A_{3} A_{4}$（这两条边不会有公共顶点，否则将出现四边形）．$\left\{B_{1}, B_{2}, B_{3}\right\}$ 中每一点都与 $\left\{A_{1}, A_{2}, A_{3}, A_{4}\right\}$ 中某一点 有边相连，$B_{1} B_{2}, B_{1} B_{3}, B_{2} B_{3}$ 都是 $G$ 中的边．由于 $\left\{B_{1}, B_{2}, B_{3} \right\}$ 都与 $\{ A_{1}, A_{2}, A_{3}, A_{4} \}$ 中某一点相连，因此至少有两个点与 $\left\{A_{1}, A_{2}\right\}$ 或 $\left\{A_{3}, A_{4}\right\}$ 中某一点相连，不妨设 $\left\{B_{1}, B_{2}, B_{3}\right\}$ 中有两点 $B_{1}, B_{2}$ 与 $\left\{A_{1}, A_{2} \right\}$ 中点有边相连这时，如果 $B_{1}, B_{2}$ 与 $\left\{A_{1}, A_{2}\right\}$ 中不同的点分别有边相连，则因为 $A_{1} A_{2}, B_{1} B_{2}$ 都是边，仍有四边形，与假设矛盾．
（iii）$\max \left(d_{1}, \cdots, d_{8}\right)>4$．取一个度数最大的顶点 $ A$，与 $A$ 有边 相连的顶点集记为 $S$，其余顶点集记为 $T$．$|S|=\max \left(d_{1}, \cdots, d_{8}\right)$ $T$ 中的点与 $S$ 中的点相连的边数至多有 $|T|$ 条，$T$ 中点相连的边数至多有 $\mathrm{C}_{|T|}^{2}$ 条，$S$ 中点相连的边至多有 $\left[\dfrac{|S|}{2}\right]$ 条这样，图中的
边数不超过 $|S|+|T|+C_{|r|}^{2}+\left[\dfrac{|S|}{2}\right]=7+C_{|r|}^{2}+\left[\dfrac{|S|}{2}\right]$ 当 $|S|=5,6,7$ 时，都不可能使边数为 $12$．综上所述，即知所求的最大值为 $11$．
答案
解析
备注
