第4题

设有 n 个顶点的图 G 满足：(i) 没有顶点与其余所有顶点都相邻；(ii) 图中不含三角形；(iii) 对任意两个不相邻的顶点 A、B，恰有一个顶点 C 同时与二者相邻。证明所有顶点的度数相同，并求可能的最小 n。

第 4/6 步：从每个

B_i

重新进行论证

上一步下一步

\deg A=\deg C_{ij}=m\Longrightarrow\deg B_i=m\quad(1\le i\le m).

详细分析

刚才的论证可概括为：以任意度数为 $r$ 的顶点为根时，所有距离为二的顶点度数都是 $r$ 。条件 (i) 排除了 $m=1$ ，所以取 $k\ne i$ 。上一步得到的 $C_{ij}$ 与某个 $C_{kh}$ 相邻，于是 $B_i$ 距离 $C_{kh}$ 为二；由于 $\deg(C_{kh})=m$ ，得到 $\deg(B_i)=m$ 。因此 $A$ 、所有 $B_i$ 和所有 $C_{ij}$ 的度数均为 $m$ 。