Moore graph
\PMlinkescapephrase
one way
Moore graphs
It is easy to see that if a graph $G$ has diameter^{} $d$ (and has any cycles at all), its girth $g$ can be no more than $2d+1$. For suppose $g\u2a7e2d+2$ and $O$ is a cycle of that minimum length $g$. Take two vertices (nodes) A and B on $O$ that are $d+1$ steps apart along $O$, one way round; they are $g(d+1)\u2a7ed+1$ steps apart the other way round. Now either there is no shorter route between A and B (contradicting diameter $d$) or there is a shorter route of length $$ creating a cycle of length $$ (contradicting girth $g$).
Definition: A Moore graph^{} is a connected graph^{} with maximal girth $2d+1$ for its diameter $d$.
Moore graphs with $d=1$, $g=3$
Diameter 1 means every vertex (node) is adjacent^{} to every other, that is, a complete graph^{}. Indeed, complete graphs ${K}_{n}$ that have cycles ($n\u2a7e3$) have triangles, so the girth is 3 and they are Moore graphs. Every valency $v\u2a7e2$ occurs (${K}_{n}$ has valency $n1$).
Moore graphs with $d=2$, $g=5$
This is the most interesting case. And http://planetmath.org/node/6948the proof that every vertex has the same valency, $v$ say, and that the graph now has $n={v}^{2}+1$ vertices in all, is easy here.
With some more work, it can be shown there are only 4 possible values for $v$ and $n$:
$v$  $n$  graph 

2  5  pentagon^{} 
3  10  Petersen graph^{} 
7  50  Hoffman–Singleton graph 
57  3250  ??? 
The first three cases each have a unique solution. The existence or otherwise of the last case is still http://planetmath.org/node/6331open. It has been shown that if it exists it has, unlike the first three, very little symmetry^{}.
The Hoffman–Singleton graph is a bit hard to draw. Here’s a unified description of the three known Moore graphs of $d=2$, all indices (mod 5):

•
Pentagon: five vertices, which we can label ${P}_{k}$.
Each ${P}_{k}$ is connected by two edges to ${P}_{k\pm 1}$.

•
Petersen: ten vertices, which we can label ${P}_{k}^{\circ}$ and ${P}_{k}^{\star}$.
Each ${P}_{k}^{\circ}$ is connected by two edges to ${P}_{k\pm 1}^{\circ}$ and by one to ${P}_{2k}^{\star}$.
Each ${P}_{k}^{\star}$ is connected by two edges to ${P}_{k\pm 1}^{\star}$ and by one to ${P}_{3k}^{\circ}$.

•
Hoffman–Singleton: fifty vertices, which we can label ${P}_{n,k}^{\circ}$ and ${P}_{m,k}^{\star}$.
Each ${P}_{n,k}^{\circ}$ is connected by two edges to ${P}_{n,k\pm 1}^{\circ}$ and by five to ${P}_{m,mn+2k}^{\star}$ for all $m$.
Each ${P}_{m,k}^{\star}$ is connected by two edges to ${P}_{m,k\pm 1}^{\star}$ and by five to ${P}_{n,2mn+3k}^{\circ}$ for all $n$.
The automorphism group^{} of the pentagon is the dihedral group^{} with 10 elements. The one of the Petersen graph is isomorphic^{} to ${S}_{5}$, with 120 elements. And the one of the HS graph is isomorphic to $\text{PSU}(3,5)\cdot 2$, with 252 000 elements, a maximal subgroup of another HS, the HigmanSims group.
Moore graphs with $d\u2a7e3$, $g\u2a7e7$
In these cases, there are only Moore graphs with valency 2, graphs consisting of a single $2d+1$gon cycle. This was proven independently by Bannai and Ito and by Damerell.
Title  Moore graph 

Canonical name  MooreGraph 
Date of creation  20130322 15:11:27 
Last modified on  20130322 15:11:27 
Owner  Mathprof (13753) 
Last modified by  Mathprof (13753) 
Numerical id  10 
Author  Mathprof (13753) 
Entry type  Definition 
Classification  msc 05C75 