Moore graph

Another equivalent definition of a Moore graph G is that it has girth g = 2k + 1 and precisely ⁠n/g⁠(m – n + 1) cycles of length g, where n and m are, respectively, the numbers of vertices and edges of G. They are in fact extremal with respect to the number of cycles whose length is the girth of the graph.

As well as having the maximum possible number of vertices for a given combination of degree and diameter, Moore graphs have the minimum possible number of vertices for a regular graph with given degree and girth.

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.

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 right hand side of the formula instead counts the number of vertices in a breadth-first search tree starting from a single vertex, accounting for the possibility that a vertex in the last level of the tree may be adjacent to d vertices in the previous level.)

[6] The even girth case also follows from the Feit-Higman theorem about possible values of n for a generalized n-gon.