強正則グラフ
srg(v, k, λ, μ) の4つのパラメータは独立ではなく、以下の関係を満たしていなければならない:
( v − k − 1 ) μ = k ( k − λ − 1 ) {\displaystyle (v-k-1)\mu =k(k-\lambda -1)}
この関係式は、数え上げ論法により非常に簡単に示すことができる。
グラフの全頂点を3つの階層に分ける。任意の頂点を1つ選んで、これは根(root)で、階層0にあるものとする。その k 個の近傍は階層1にあるとし、それ以外の全ての頂点は階層2にあるとする。
階層1の頂点は根と直接つながっているので、根と共有する近傍が λ 個あることになり、これらは階層1にある。どの頂点の次数も k だから、階層1の頂点が持つ階層2の頂点との辺は、残った k − λ − 1 {\displaystyle k-\lambda -1} 本である。よって階層1と階層2の間には合計 k × ( k − λ − 1 ) {\displaystyle k\times (k-\lambda -1)} 本の辺がある。
階層2の頂点は根と直接つながっていないので、根と共有する近傍が μ 個あることになり、これらは全て階層1になければいけない。階層2の頂点は ( v − k − 1 ) {\displaystyle (v-k-1)} 個で、どの頂点も階層1の頂点 μ 個とつながっている。よって階層1と階層2の間には合計 ( v − k − 1 ) × μ {\displaystyle (v-k-1)\times \mu } 本の辺がある。
階層1と階層2の間にある辺の本数を表す2つの表現を等しいと置けばよい。