第4問

n 頂点グラフ G が次を満たすとする。(i) どの頂点も他のすべての頂点と隣接しない。(ii) 三角形を含まない。(iii) 隣接しない任意の2頂点 A,B に対し、両方に隣接する頂点 C がちょうど1つ存在する。すべての頂点の次数が等しいことを示し、可能な最小の 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 である。5サイクルは三角形を含まず、全頂点に隣接する頂点もなく、隣接しない各頂点対がちょうど1つの共通隣人を持つ。したがってすべての条件を満たし、n=5 を実現する。