Moore graphs of d=2 are v-valent and order is v2+1

Given a Moore graphMathworldPlanetmath with diameterMathworldPlanetmathPlanetmath 2 and girth 5, which implies the existence of cycles. To prove every node (vertex) has the same valencyPlanetmathPlanetmath, v say, and the number n of nodes (vertices) is v2+1.

Lemma: a key feature of Moore graphs with diameter 2 is that any nodes X and that are not adjacentPlanetmathPlanetmathPlanetmath have exactly one shared neighbour Y. Proof of lemma: at least one Yk because distanceMathworldPlanetmath XY is not 1 so must be 2, at most one because XY0ZY1 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 Ai), and nodes at distance 1 from C and 2 from B (call them Dj). Now no cycle can exist (the only edges are AiB, BC, CDj; 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 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 o other neighbours Ni and let Q have q other neighbours Rj.


No Ni can be adjacent to P (3-cycle PONi) so the unique joint neighbours of any Ni and Q must be among the Rj. Different Ni and Ni cannot use the same Rj (4-cycle ONiRjNi) so we have oq. By the same argument (swapping O and Q, Ni and Rj) also qo so we have o=q, both nodes have valency q+1

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. 

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 Oi and R has q other neighbours Qj. Call the joint neighbour of Oi and Qj now Pij, these q2 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: q2+2q+2=(q+1)2+1, for valency q+1

Title Moore graphs of d=2 are v-valent and order is v2+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