The formula for the number of vertices in a Moore graph can be generalized to allow a definition of Moore graphs with even girth as well as odd girth.
Let G be any graph with maximum degree d and diameter k, and consider the tree formed by breadth first search starting from any vertex v. This tree has 1 vertex at level 0 (v itself), and at most d vertices at level 1 (the neighbors of v). In the next level, there are at most d(d-1) vertices: each neighbor of v uses one of its adjacencies to connect to v and so can have at most d-1 neighbors at level 2. In general, a similar argument shows that at any level 1 ≤ i ≤ k, there can be at most d(d-1)i vertices. Thus, the total number of vertices can be at most
Later, showed that Moore graphs can equivalently be defined as having diameter k and girth 2k+1; these two requirements combine to force the graph to be d-regular for some d and to satisfy the vertex-counting formula.
Instead of upper bounding the number of vertices in a graph in terms of its maximum degree and its diameter, we can calculate via similar methods a lower bound on the number of vertices in terms of its minimum degree and its girth. Suppose G has minimum degree d and girth 2k+1. Choose arbitrarily a starting vertex v, and as before consider the breadth-first search tree rooted at v. This tree must have one vertex at level 0 (v itself), and at least d vertices at level 1. At level 2 (for k > 1), there must be at least d(d-1) vertices, because each vertex at level 1 has at least d-1 remaining adjacencies to fill, and no two vertices at level 1 can be adjacent to each other or to a shared vertex at level 2 because that would create a cycle shorter than the assumed girth. In general, a similar argument shows that at any level 1 ≤ i ≤ k, there must be at least d(d-1)i vertices. Thus, the total number of vertices must be at least
For even girth 2k, one can similarly form a breadth-first search tree starting from the midpoint of a single edge. The resulting bound on the minimum number of vertices in a graph of this girth with minimum degree d is
The Hoffman–Singleton theorem states that any Moore graph with girth 5 must have degree 2, 3, 7, or 57. The graphs with degree 2, 3, and 7 are the pentagon, Petersen graph, and Hoffman–Singleton graph, respectively. It is not known whether a Moore graph with girth 5 and degree 57 exists.
If the generalized definition of Moore graphs that allows even girth graphs is used, the Moore graphs also include the complete bipartite graph Kn,n with girth four, the Heawood graph with degree 3 and girth 6, and the Tutte–Coxeter graph with degree 3 and girth 8. More generally, it is known that, other than the graphs listed above, all Moore graphs must have girth 5, 6, 8, or 12.