第4题

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

第 5/6 步：计算顶点数

n=1+m+m(m-1)=m^2+1.

详细分析

顶点包括 A、它的 m 个邻点 B_i，以及每个 B_i 的另外 m-1 个邻点。由唯一性条件，这些后者的集合两两不交，且不存在距离超过二的顶点。因此 n=m^2+1。