[proofplan] A Moore graph is a $(k, 0, 1)$-strongly regular graph on $n = k^2 + 1$ vertices. Substituting these parameters into the integrality constraint from [Strongly Regular Graphs are Rare](/theorems/2065) forces the discriminant $\sqrt{4k-3}$ to be rational, hence an integer $m$. Writing $m = 2s + 1$ yields $k = s^2 + s + 1$ in terms of a non-negative integer $s$. A second integrality constraint — derived from the multiplicity formula with the substituted parameters — produces a polynomial divisibility condition $s(s-1)(s+1)(s+2) \mid 32$ (equivalently, $m \mid 15$), which restricts $m \in \{1, 3, 5, 15\}$ and consequently $k \in \{2, 3, 7, 57\}$. The case $k = 1$ is excluded because a Moore graph with $k = 1$ is not diameter-$2$. [/proofplan] [step:Substitute the Moore graph parameters $(k, 0, 1)$ and $n = k^2 + 1$ into the integrality condition] A [Moore graph](/page/Moore%20Graph) with $\Delta(G) = k$ is by definition a $k$-regular graph of girth $5$ and diameter $2$, and is equivalently characterised as a $(k, 0, 1)$-strongly regular graph on $n = k^2 + 1$ vertices. (Girth $5$ gives $a = 0$: adjacent vertices have no common neighbour, else a triangle would form. Diameter $2$ and girth $5$ together give $b = 1$: any two non-adjacent vertices have exactly one common neighbour, else a $4$-cycle would form. The vertex count $n = k^2 + 1$ follows by counting the ball of radius $1$ around a fixed vertex: the vertex itself, its $k$ neighbours, and for each neighbour its $k - 1$ further neighbours, all distinct by girth $5$, giving $1 + k + k(k-1) = k^2 + 1$.) We apply [Strongly Regular Graphs are Rare](/theorems/2065). Theorem 2065 requires $G$ to be a $(k, a, b)$-strongly regular graph; we verify this holds with $a = 0$, $b = 1$, $n = k^2 + 1$. We substitute these values into the two integrality expressions. First, the discriminant: \begin{align*} (a - b)^2 + 4(k - b) = (0 - 1)^2 + 4(k - 1) = 4k - 3. \end{align*} Second, the numerator inside the fraction: \begin{align*} (n - 1)(b - a) - 2k = k^2 \cdot 1 - 2k = k^2 - 2k = k(k - 2). \end{align*} Finally, $n - 1 = k^2$. The integrality condition thus becomes \begin{align*} \frac{1}{2}\!\left(k^2 \pm \frac{k(k - 2)}{\sqrt{4k - 3}}\right) \in \mathbb{Z}. \tag{$\star$} \end{align*} [guided] Theorem 2065 gives us the integrality condition \begin{align*} \frac{1}{2}\!\left((n-1) \pm \frac{(n-1)(b-a) - 2k}{\sqrt{(a-b)^2 + 4(k-b)}}\right) \in \mathbb{Z}. \end{align*} To apply it, we need to know that a Moore graph really is strongly regular, with which parameters. **Definition check.** A Moore graph is a $k$-regular graph of girth $5$ and diameter $2$. Equivalently (and this is the characterisation we use), it is a $(k, 0, 1)$-strongly regular graph on $n = k^2 + 1$ vertices: - $a = 0$: if two adjacent vertices shared a common neighbour, we would have a triangle, contradicting girth $\geq 5$. - $b = 1$: two non-adjacent vertices must have at least one common neighbour (diameter $\leq 2$); they cannot have two, else two such common neighbours would form a $4$-cycle, contradicting girth $\geq 5$. - $n = k^2 + 1$: count the $2$-ball around a fixed vertex $v$. It contains $v$ itself ($1$ vertex), the $k$ neighbours of $v$, and from each neighbour $u$ a further $k - 1$ vertices (its neighbours other than $v$). Girth $5$ guarantees these $k(k-1)$ second-neighbours are distinct and disjoint from the first ball. Diameter $2$ guarantees every vertex lies in this ball. Total: $1 + k + k(k-1) = k^2 + 1$. **Hypothesis check for Theorem 2065.** Theorem 2065 requires the graph to be $(k, a, b)$-strongly regular, which we have just verified with the values $k, a = 0, b = 1$. **Substitute.** Compute each piece of the formula with $a = 0$, $b = 1$, $n - 1 = k^2$: \begin{align*} (a - b)^2 + 4(k - b) &= 1 + 4(k - 1) = 4k - 3, \\ (n - 1)(b - a) - 2k &= k^2 \cdot (1 - 0) - 2k = k^2 - 2k = k(k-2). \end{align*} So the integrality condition becomes \begin{align*} \frac{1}{2}\!\left(k^2 \pm \frac{k(k-2)}{\sqrt{4k-3}}\right) \in \mathbb{Z}. \tag{$\star$} \end{align*} This is the condition we will now analyse. [/guided] [/step] [step:Handle the degenerate half-case $k = 2$ separately] If $k = 2$, then $k(k-2) = 0$, and $(\star)$ reduces to $\frac{1}{2}(k^2) = \frac{1}{2}(4) = 2 \in \mathbb{Z}$, which holds. So $k = 2$ is admissible. The Moore graph of degree $2$ is the $5$-cycle $C_5$ (a $2$-regular graph of girth $5$ and diameter $2$ on $5 = 2^2 + 1$ vertices). For the remainder of the proof, assume $k \geq 3$, so that $k(k-2) \neq 0$ and the fraction in $(\star)$ is nonzero. [/step] [step:Force $\sqrt{4k-3}$ to be an integer by rationality of the expression] Assume $k \geq 3$. For $(\star)$ to be an integer, the quantity \begin{align*} \frac{k(k-2)}{\sqrt{4k-3}} \end{align*} must be rational, since it equals $2 \cdot [(\star)] - k^2$ after choosing a sign, and the right-hand side is rational. Since $k(k-2) \neq 0$ is an integer, rationality of the fraction forces $\sqrt{4k-3}$ to be rational. But $4k - 3 \in \mathbb{Z}_{\geq 1}$, and a [rational square root of a positive integer is itself an integer](/theorems/???). Thus $\sqrt{4k - 3} = m$ for some positive integer $m$, i.e. \begin{align*} 4k - 3 = m^2. \tag{$\dagger$} \end{align*} From $4k - 3 = m^2$ we read off $m^2 \equiv -3 \equiv 1 \pmod{4}$, hence $m$ is odd. Write $m = 2s + 1$ for some non-negative integer $s \geq 1$ (since $k \geq 3$ gives $m^2 = 4k - 3 \geq 9$, so $m \geq 3$, so $s \geq 1$). Then \begin{align*} 4k - 3 = (2s + 1)^2 = 4s^2 + 4s + 1 \quad \Longrightarrow \quad k = s^2 + s + 1. \end{align*} [guided] **Why must $\sqrt{4k-3}$ be an integer?** Look at $(\star)$. The expression $\frac{1}{2}(k^2 \pm \frac{k(k-2)}{\sqrt{4k-3}})$ lies in $\mathbb{Z}$, so in particular it is rational. Since $\frac{1}{2} k^2$ is rational, the other summand $\frac{1}{2} \cdot \frac{k(k-2)}{\sqrt{4k-3}}$ is also rational. Multiplying by $2$ and by the nonzero integer $k(k-2)$, we find that $\frac{1}{\sqrt{4k-3}}$ is rational, hence $\sqrt{4k-3}$ is rational. But $4k - 3$ is a positive integer, and if the square root of a positive integer is rational, then the integer is a perfect square. (Proof sketch: if $\sqrt{N} = p/q$ in lowest terms, then $q^2 N = p^2$, so $q \mid p$, forcing $q = 1$ and $\sqrt{N} = p \in \mathbb{Z}$.) So $4k - 3 = m^2$ for some positive integer $m$. **Parity of $m$.** Reducing $m^2 = 4k - 3$ modulo $4$: $m^2 \equiv -3 \equiv 1 \pmod{4}$, so $m$ is odd. Write $m = 2s + 1$. **Lower bound on $s$.** Our standing assumption is $k \geq 3$, so $m^2 = 4k - 3 \geq 9$, giving $m \geq 3$, hence $s \geq 1$. **Express $k$ in terms of $s$.** Square: $m^2 = 4s^2 + 4s + 1$. Equating to $4k - 3$: \begin{align*} 4k - 3 = 4s^2 + 4s + 1 \quad \Longleftrightarrow \quad k = s^2 + s + 1. \end{align*} Good — we have parametrised the admissible values of $k$ by a single integer parameter $s$. But not every $s$ gives a valid Moore graph: we have only used that a certain rationality condition holds. We must now impose the full integrality from $(\star)$. [/guided] [/step] [step:Impose the integrality of the multiplicity and derive the divisibility $m \mid 15$] Substitute $m = \sqrt{4k-3}$ and $k = s^2 + s + 1$ into the numerator: \begin{align*} k(k - 2) = (s^2 + s + 1)(s^2 + s - 1) = (s^2 + s)^2 - 1. \end{align*} Also $k^2 = (s^2 + s + 1)^2$. The integrality condition $(\star)$ becomes \begin{align*} \frac{1}{2}\!\left((s^2 + s + 1)^2 \pm \frac{(s^2 + s)^2 - 1}{m}\right) \in \mathbb{Z}. \tag{$\star\star$} \end{align*} The first summand $\frac{1}{2}(s^2 + s + 1)^2$ is $\frac{1}{2}$ times an odd integer squared (since $s^2 + s = s(s+1)$ is even, so $s^2 + s + 1$ is odd, so its square is odd); hence it is a half-integer with fractional part $\frac{1}{2}$. For the sum to be an integer, the second summand must also have fractional part $\frac{1}{2}$; in particular, $\frac{(s^2 + s)^2 - 1}{m}$ must be an integer of the correct parity. We focus first on the integrality: we need \begin{align*} m \bigm| (s^2 + s)^2 - 1 = (s^2 + s - 1)(s^2 + s + 1). \tag{div} \end{align*} Now $m = 2s + 1$. We reduce each factor modulo $m$. From $2s \equiv -1 \pmod{m}$, squaring: $4s^2 \equiv 1 \pmod{m}$, so $s^2 \equiv 4^{-1} \pmod{m}$ whenever $\gcd(4, m) = 1$ — and indeed $m$ is odd, so $4$ is invertible mod $m$. Multiplying the congruence $2s \equiv -1$ by $2$: $4s \equiv -2$, so $s \equiv -2 \cdot 4^{-1} \pmod m$. Consequently \begin{align*} 4(s^2 + s) \equiv 1 + 4s \equiv 1 - 2 = -1 \pmod{m}, \end{align*} i.e., $s^2 + s \equiv -4^{-1} \pmod m$, so \begin{align*} (s^2 + s)^2 \equiv 16^{-1} \pmod{m}. \end{align*} Hence $(s^2 + s)^2 - 1 \equiv 16^{-1} - 1 = (1 - 16) \cdot 16^{-1} = -15 \cdot 16^{-1} \pmod{m}$. The divisibility $(\text{div})$ therefore reduces to \begin{align*} m \bigm| 15. \tag{$\ddagger$} \end{align*} [guided] **Setup.** Plug $k = s^2 + s + 1$ into the fraction in $(\star)$. The numerator is \begin{align*} k(k - 2) = (s^2 + s + 1)(s^2 + s - 1), \end{align*} which we recognise as a difference of squares: letting $u = s^2 + s$, this is $(u+1)(u-1) = u^2 - 1 = (s^2+s)^2 - 1$. The denominator is $m = 2s + 1$. **Integrality of the quotient.** For the $\pm$ half of $(\star)$ to lie in $\frac{1}{2}\mathbb{Z}$ (to combine with $\frac{1}{2}k^2$ to give an integer), we need \begin{align*} \frac{(s^2+s)^2 - 1}{m} \in \mathbb{Z} \end{align*} (plus a parity compatibility we address in the next step). So $m$ must divide $(s^2 + s)^2 - 1$. **Computing modulo $m$.** We want to express $(s^2 + s)^2 - 1$ mod $m$ in terms that do not involve $s$. Start from the defining congruence \begin{align*} m = 2s + 1 \implies 2s \equiv -1 \pmod{m}. \end{align*} Since $m$ is odd, $2$ is invertible mod $m$; call $2^{-1}$ its inverse. Then $s \equiv -2^{-1} \pmod m$, so \begin{align*} s^2 + s \equiv (2^{-1})^2 - 2^{-1} = \frac{1}{4} - \frac{1}{2} = -\frac{1}{4} \pmod{m}, \end{align*} where $1/4$ denotes $4^{-1} \pmod m$. Squaring: \begin{align*} (s^2 + s)^2 \equiv \frac{1}{16} \pmod m. \end{align*} Thus \begin{align*} (s^2+s)^2 - 1 \equiv \frac{1}{16} - 1 = -\frac{15}{16} \pmod{m}. \end{align*} Because $\gcd(16, m) = 1$, multiplying by $16$ preserves divisibility by $m$: \begin{align*} m \mid (s^2 + s)^2 - 1 \iff m \mid 16 \cdot ((s^2+s)^2 - 1) \equiv -15 \pmod m \iff m \mid 15. \end{align*} [/guided] [/step] [step:Enumerate the divisors and translate back to $k$] The positive odd divisors of $15$ are $1, 3, 5, 15$. From $m \geq 3$ (in the $k \geq 3$ case) we get $m \in \{3, 5, 15\}$; including the separately-handled $k = 2$ case (which corresponds to $m = \sqrt{5}$, not an integer — indeed $k = 2$ was the degenerate case where the fraction vanished and no integrality of $\sqrt{4k-3}$ was required). Using $m = 2s + 1$ and $k = s^2 + s + 1$: \begin{align*} \begin{array}{c|c|c|c} m & s = (m-1)/2 & k = s^2 + s + 1 & n = k^2 + 1 \\ \hline 1 & 0 & 1 & 2 \\ 3 & 1 & 3 & 10 \\ 5 & 2 & 7 & 50 \\ 15 & 7 & 57 & 3250 \end{array} \end{align*} The case $m = 1$ gives $k = 1$, which does not correspond to a Moore graph: a $1$-regular connected graph on $2$ vertices is $K_2$, which has diameter $1$, not $2$. We exclude it. Combining with the $k = 2$ case handled earlier, we conclude \begin{align*} k \in \{2, 3, 7, 57\}. \end{align*} [guided] **Enumerate divisors.** The positive divisors of $15$ are $1, 3, 5, 15$; all are odd (as required, since $m$ must be odd). **Tabulate.** For each $m$, we recover $s = (m-1)/2$ and then $k = s^2 + s + 1$: \begin{align*} m = 1: \quad s = 0, \quad k = 0 + 0 + 1 = 1, \\ m = 3: \quad s = 1, \quad k = 1 + 1 + 1 = 3, \\ m = 5: \quad s = 2, \quad k = 4 + 2 + 1 = 7, \\ m = 15: \quad s = 7, \quad k = 49 + 7 + 1 = 57. \end{align*} **Discard $k = 1$.** A $1$-regular graph is a disjoint union of edges; the only connected $1$-regular graph is $K_2$, which has diameter $1$. So $k = 1$ does not yield a Moore graph, and we exclude this case. **Include $k = 2$.** The $5$-cycle $C_5$ is a Moore graph of degree $2$: it is $2$-regular, has girth $5$, and has diameter $2$ (the "opposite" vertex on the cycle is at distance $2$). Thus $k = 2$ is genuinely allowed — we handled it in the earlier degenerate case, where the fraction in $(\star)$ vanished because $k - 2 = 0$. **Conclusion.** The only possible degrees are \begin{align*} k \in \{2, 3, 7, 57\}. \end{align*} This completes the proof. (Historical note. Moore graphs actually exist for $k = 2$ (the pentagon $C_5$), $k = 3$ (the Petersen graph), and $k = 7$ (the Hoffman–Singleton graph). Whether a Moore graph of degree $57$ exists is a famous open problem in algebraic graph theory; this theorem says only that no other degree is possible.) [/guided] [/step]