第4問

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

ステップ 4/6: 各

B_i

で議論を繰り返す

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

\deg A=\deg C_{ij}=m\Longrightarrow\deg B_i=m\quad(1\le i\le m).

詳しい解説

直前の議論は一般に、次数 $r$ の任意の根から距離2にあるすべての頂点の次数が $r$ であることを示す。条件 (i) により $m=1$ ではないので $k\ne i$ を取る。前段で得た $C_{ij}$ とある $C_{kh}$ の辺により、 $B_i$ は $C_{kh}$ から距離2にある。 $\deg(C_{kh})=m$ だから $\deg(B_i)=m$ 。したがって $A$ 、すべての $B_i$ 、すべての $C_{ij}$ の次数は $m$ である。