第4問

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

ステップ 3/6:

C_{ij}

の次数を数える

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

\deg(C_{ij})=1+(m-1)=m.

詳しい解説

$B_i$ 以外で $C_{ij}$ に隣接する頂点は、ある $C_{hk}$ に限られる。 $A$ なら $A,B_i$ と三角形を作り、 $B_k$ ( $k\ne i$ ) なら隣接しない組 $B_i,B_k$ が $A$ と $C_{ij}$ という2つの共通隣人を持つからである。各 $k\ne i$ について $C_{ij}$ に隣接できる $C_{kh}$ は高々1つである。2つあれば $B_k$ と $C_{ij}$ の共通隣人が2つになる。 $B_k,C_{ij}$ は隣接しないので共通隣人がちょうど1つあり、それは $A$ ではなくそのような $C_{kh}$ である。従って各 $k\ne i$ に1つずつ存在し、 $\deg(C_{ij})=1+(m-1)=m$ 。