Un graphe de Moore est un graphe régulier de degré d et de diamètre k qui possède un nombre de sommets égal à la borne supérieure :
De façon générale, le nombre de sommets d'un graphe de degré maximal d et de diamètre k est inférieur ou égal à cette valeur. Un graphe de Moore possède donc une valeur maximale de sommets pour un degré et un diamètre donnés.
De façon alternative, un graphe de Moore est un graphe régulier de diamètre k et de maille 2k+1. Cette définition est équivalente à la précédente.
Il est possible de généraliser la définition pour permettre à un graphe de Moore d'être de maille paire. Dans ce cas, un graphe de Moore est un graphe régulier de degré d>2 et de maille m dont le nombre de sommets est égal à :
si m est pair, et
si m est impair.
