MathLabs

第4問

n 頂点グラフ G が次を満たすとする。(i) どの頂点も他のすべての頂点と隣接しない。(ii) 三角形を含まない。(iii) 隣接しない任意の2頂点 A,B に対し、両方に隣接する頂点 C がちょうど1つ存在する。すべての頂点の次数が等しいことを示し、可能な最小の n を求めよ。
ステップ 5/6: 頂点数を数える
n=1+m+m(m−1)=m2+1.n=1+m+m(m-1)=m^2+1.
詳しい解説

頂点は A、その m 個の隣人 B_i、および各 B_i に対するさらに m-1 個の隣人からなる。後者の集合は一意性条件により互いに素であり、距離2を超える頂点は存在しない。従って n=m^2+1 である。