|
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,  say, and the number  of nodes (vertices) is  .
Lemma: a key feature of Moore graphs with diameter 2 is that any nodes X and Z that are not adjacent have exactly one shared neighbour Y. Proof of lemma: at least one Y because distance XY is not 1 so must be 2, at most one because XY ZY would be a 4-cycle.
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 ), and nodes at distance 1 from C and 2 from B (call them D ). Now no cycle can exist (the only edges are A B, BC, CD ; any edge of type AA, AC, AD, 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  D, otherwise BAC would be a 3-cycle). Now CDEAB is a 5-cycle with edge BC.
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  other neighbours N and let Q have  other neighbours R .
No N can be adjacent to P (3-cycle PON ) so the unique joint neighbours of any N and Q must be among the R . Different N and N cannot use the same R (4-cycle ON R N ) so we have  . By the same argument (swapping O and Q, N and R ) also  so we have  , both nodes have valency  .
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  , both O and S have that same valency by the previous lemma.
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  ).
Now let N and R be any two adjacent nodes. N has  other neighbours O and R has  other neighbours Q . Call the joint neighbour of O and Q now P , these  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  from N or R otherwise). Tally:
 , for valency  .
| 
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
![\begin{picture}(100,110)(-50,-55) \par \put(+44,+27){\circle{12}} \put( -7,+44){... ...(0,0)[rt]{\small Q}} \put(+54,-27){\makebox(0,0)[l]{\small R$_j$}} \end{picture}](http://images.planetmath.org:8080/cache/objects/6948/l2h/img18.png "\begin{picture}(100,110)(-50,-55) \par \put(+44,+27){\circle{12}} \put( -7,+44){... ...(0,0)[rt]{\small Q}} \put(+54,-27){\makebox(0,0)[l]{\small R$_j$}} \end{picture}")
![\begin{picture}(100,110)(-50,-55) \par \put(-44,+27){\circle*{4}} \put( +7,+44){... ...x(0,0)[t]{\small Q$_j$}} \put(-50,-30){\makebox(0,0)[r]{\small R}} \end{picture}](http://images.planetmath.org:8080/cache/objects/6948/l2h/img39.png "\begin{picture}(100,110)(-50,-55) \par \put(-44,+27){\circle*{4}} \put( +7,+44){... ...x(0,0)[t]{\small Q$_j$}} \put(-50,-30){\makebox(0,0)[r]{\small R}} \end{picture}")