# 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. $\circ {}^{\circ}\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 $\ne $ D, otherwise BAC would be a 3-cycle). Now CDEAB is a 5-cycle with edge BC. $\circ {}^{\circ}\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\u2a7dq$. By the same argument (swapping O and Q, N${}_{i}$ and R${}_{j}$) also $q\u2a7do$ so we have $o=q$, both nodes have valency $q+1$. $\circ {}^{\circ}\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. $\circ {}^{\circ}\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$. $\circ {}^{\circ}\circ $

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

Canonical name | MooreGraphsOfD2AreVvalentAndOrderIsV21 |

Date of creation | 2013-03-22 15:11:30 |

Last modified on | 2013-03-22 15:11:30 |

Owner | marijke (8873) |

Last modified by | marijke (8873) |

Numerical id | 6 |

Author | marijke (8873) |

Entry type | Proof |

Classification | msc 05C75 |