第4問

n 頂点グラフ G が次を満たすとする。(i) どの頂点も他のすべての頂点と隣接しない。(ii) 三角形を含まない。(iii) 隣接しない任意の2頂点 A,B に対し、両方に隣接する頂点 C がちょうど1つ存在する。すべての頂点の次数が等しいことを示し、可能な最小の n を求めよ。

ステップ 2/6: 距離2の頂点を区別する

前のステップ次のステップ

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$ とその頂点という2つの共通隣人を持つからである。任意の頂点 $X$ は、 $A$ 自身か、 $A$ に隣接するか、 $A$ と隣接せず (iii) により $A$ と共通隣人を持つかのいずれかである。したがって $\operatorname{dist}(A,X)\le2$ 。