第4题

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

第 6/6 步：求最小值并给出构造

m=1\Rightarrow n=2\text{ violates (i)};\qquad m=2\Rightarrow n=5,\quad C_5\text{ works}.

详细分析

若 m=1，则 n=2，每个顶点都与所有其他顶点相邻，违反条件 (i)。所以 m≥2 且 n≥5。五边形环不含三角形，没有与所有其他顶点相邻的顶点，并且每对不相邻顶点恰有一个公共邻点；因此它满足全部条件并实现 n=5。