ムーアグラフ
Gを次数d、直径kの任意のグラフとする。頂点vをルートとして幅優先探索木を構成する。この木は0階層に1つの頂点(v自身)、1階層に高々d個の頂点がある。次の階層には高々d(d-1)個の頂点がある。というのは、2階層において、1階層目の頂点は0階層のvと隣接しているため2階層目と高々d-1の頂点と隣接する。同様の議論によって一般的に、i階層目(1 ≤ i ≤ k)には高々d(d-1) 個の頂点が存在する。よって各階層の頂点数を足し上げると次式を得る。
1 + d ∑ i = 0 k − 1 ( d − 1 ) i . {\displaystyle 1+d\sum _{i=0}^{k-1}(d-1)^{i}.}
ムーアグラフはホフマンとシングルトンによってこの上限に頂点数が一致するグラフとして定義された。ムーアグラフは次数d、直径kのグラフのうち頂点数が最大のものである。
その後、Singleton (1968) によって、ムーアグラフは直径k、内周2k+1を満たすグラフと同値であることが示された。直径と内周の条件によってグラフは正則となる。