ムーアグラフ
ムーアグラフは最大次数と直径が与えられたときに最大頂点数のグラフとして定式化されるが、類似の議論によって最小次数と内周が与えられたときに最小頂点数のグラフとしても定式化されうる(Erdős, Rényi & Sós 1966).。Gを最小次数dと内周2k+1をもつ任意のグラフとしよう。任意の頂点vから始めて幅優先探索木を構成する。0階層にはちょうど1つのv自身が存在する。また1階層には少なくともd個の頂点が存在する。 2階層(k > 1)には, 少なくともd(d-1)個の頂点が存在する。なぜなら1階層の異なる2頂点は内周の制約から2階層に共通の近傍を持たないからだ。同様にして一般的に任意の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}.