第4题

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

第 2/6 步：区分距离为二的顶点

C_{ij}\ne C_{hk}\text{ for distinct pairs }(i,j)\ne(h,k);\qquad\operatorname{dist}(A,X)\le2.

详细分析

所有 $C_{ij}$ 都彼此不同：若某个顶点同时邻接不同的 $B_i$ 和 $B_h$ ，则不相邻的那一对会有 $A$ 和该顶点两个公共邻点。任意顶点 $X$ 要么是 $A$ ，要么与 $A$ 相邻，要么不与 $A$ 相邻而由条件 (iii) 与 $A$ 有公共邻点。因此 $\operatorname{dist}(A,X)\le2$ 。