どの頂点からも辺がd本でていて、どの２頂点距離2以下であるグラフを考える。K5やK3,3

このグラフの頂点数は高々d^2+1である。

ちょうどd^2+1のグラフをムーア・グラフという。

ムーア・グラフはd=0,1,2,3,7,57以外には存在しないことが証明されている。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

知られている最大のムーア・グラフの頂点数は50で、d=57の時の存在するかどうかは未解決である。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝