第4题

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

第 1/6 步：选择一个顶点并命名其邻点

N(A)=\{B_1,\ldots,B_m\},\qquad\deg A=m.

详细分析

取度数为 $m$ 的顶点 $A$ ，将其邻点记为 $B_1,\ldots,B_m$ 。任意两个 $B_i$ 都不能相邻，否则它们与 $A$ 构成三角形。对每个 $i$ ，把 $B_i$ 除 $A$ 以外的 $\deg(B_i)-1$ 个邻点记为 $C_{ij}$ 。