# Moore graphs of $d=2$ are $v$-valent and order is $v^{2}+1$

Given a Moore graph with diameter 2 and girth 5, which implies the existence of cycles. To prove every node (vertex) has the same valency, $v$ say, and the number $n$ of nodes (vertices) is $v^{2}+1$.

Lemma: a key feature of Moore graphs with diameter 2 is that any nodes X and that are not adjacent have exactly one shared neighbour Y. Proof of lemma: at least one Y${}_{k}$ because distance XY is not 1 so must be 2, at most one because XY${}_{0}$ZY${}_{1}$ would be a 4-cycle.  ${\scriptstyle\circ}\!{}^{\circ}\!{\scriptstyle\circ}$

Lemma: every two adjacent nodes B and C lie together on some 5-cycle. Proof of lemma: every node (other than B) is at distance 1 or 2 from B, and every node (other than C) at distance 1 or 2 from C. There are no nodes X at distance 1 from both (BXC would be a 3-cycle). Suppose the graph only has nodes at distance 1 from B and 2 from C (call them A${}_{i}$), and nodes at distance 1 from C and 2 from B (call them D${}_{j}$). Now no cycle can exist (the only edges are A${}_{i}$B, BC, CD${}_{j}$; any edge of type AA, AC, , BD, DD would create a 3-or 4-cycle). But Moore graphs have cycles by definition. So there must be at least one node E at distance 2 from both B and C. Let A be the joint neighbour of B and E, and D that of C and E (note A $\neq$ D, otherwise BAC would be a 3-cycle). Now CDEAB is a 5-cycle with edge BC.  ${\scriptstyle\circ}\!{}^{\circ}\!{\scriptstyle\circ}$

Lemma: two nodes O and Q at distance 2 have the same valency. Proof of lemma: let P be the unique joint neighbour. Let O have $o$ other neighbours N${}_{i}$ and let Q have $q$ other neighbours R${}_{j}$.

No N${}_{i}$ can be adjacent to P (3-cycle PON${}_{i}$) so the unique joint neighbours of any N${}_{i}$ and Q must be among the R${}_{j}$. Different N${}_{i}$ and N${}_{i^{\prime}}$ cannot use the same R${}_{j}$ (4-cycle ON${}_{i}$R${}_{j}$N${}_{i^{\prime}}$) so we have $o\leqslant q$. By the same argument (swapping O and Q, N${}_{i}$ and R${}_{j}$) also $q\leqslant o$ so we have $o=q$, both nodes have valency $q+1$${\scriptstyle\circ}\!{}^{\circ}\!{\scriptstyle\circ}$

Lemma: two adjacent nodes O and S have the same valency. Proof of lemma: let OPQRS be the 5-cycle through SO. Calling the valency of Q again $q+1$, both O and S have that same valency by the previous lemma.  ${\scriptstyle\circ}\!{}^{\circ}\!{\scriptstyle\circ}$

Proof of theorem: the graph is connected. Travel from any node to any other via adjacent ones, the valency stays the same by the last lemma (let’s keep calling it $q+1$).

Now let N and R be any two adjacent nodes. N has $q$ other neighbours O${}_{i}$ and R has $q$ other neighbours Q${}_{j}$. Call the joint neighbour of O${}_{i}$ and Q${}_{j}$ now P${}_{ij}$, these $q^{2}$ nodes are all distinct (4-cycles of type NOPO and/or RQPQ otherwise) and none of them coincide with N, R, the Os or Qs (3- or 4-cycles otherwise). On the other hand, there are no further nodes (distance $>2$ from N or R otherwise). Tally: $q^{2}+2q+2=(q+1)^{2}+1$, for valency $q+1$${\scriptstyle\circ}\!{}^{\circ}\!{\scriptstyle\circ}$

Title Moore graphs of $d=2$ are $v$-valent and order is $v^{2}+1$ MooreGraphsOfD2AreVvalentAndOrderIsV21 2013-03-22 15:11:30 2013-03-22 15:11:30 marijke (8873) marijke (8873) 6 marijke (8873) Proof msc 05C75