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⩽q$. By the same argument (swapping O and Q, N${}_i$ and R${}_j$) also $q⩽o$ 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