第4問

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

ステップ 1/6: 頂点を選び、その隣接頂点に名前を付ける

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

N(A)=\{B_1,\ldots,B_m\},\qquad\deg A=m.

詳しい解説

次数 $m$ の頂点 $A$ を選び、その隣接頂点を $B_1,\ldots,B_m$ とする。 $B_i$ 同士は隣接できない。そうでなければ $A$ とともに三角形を作るからである。各 $i$ について、 $A$ 以外の $B_i$ の隣接頂点 $\deg(B_i)-1$ 個を $C_{ij}$ と名付ける。