Moore Graph Existence

A Degree-Fifty-Seven Moore Graph

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A diameter-two Moore graph of degree $d$ attains the breadth-first-search bound $1+d+d(d-1)=d^2+1$. For $d=57$ the required graph has 3250 vertices, is 57-regular and has girth five. Equivalently it is strongly regular with parameters $(3250,57,0,1)$. No transitivity assumption is part of the question. [S1] [S2]

Statement recorded in the supplied source.

Does a Moore graph with girth 5 and degree 57 exist? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Construct the 3250-vertex graph or derive a contradiction from its required strongly regular and automorphism structure. [S1]

Short English statement

Does the exceptional possible Moore graph of degree fifty-seven and 3,250 vertices actually exist?

Research attempt

Scope and conflicting literature claims.

The question is existence without any transitivity assumption. The title of [S4] alone is not treated as a proof of nonexistence: Faber and Keegan [E1] discuss why the problem remains unresolved. Ishida's 2026 manuscript [E2] concerns involutions in an automorphism group; even exclusion of all involutions would not exclude an asymmetric graph. The route here derives exact local and matrix conditions and tests their smaller-degree analogue.

The global matrix and its feasible spectrum.

Let $A$ be the adjacency matrix of a putative graph. No adjacent pair has a common neighbour, and every nonadjacent pair has exactly one. Therefore \[ A^2=56I-A+J, \qquad A\mathbf1=57\mathbf1. \] On $\mathbf1^\perp$, the eigenvalues solve $r^2+r-56=0$, giving $7$ and $-8$. The multiplicity equations are \[ f+g=3249,\qquad57+7f-8g=0, \qquad f=1729,\quad g=1520. \] The integer multiplicities and the trace of $A^2$, namely $3250\cdot57$, are consistent. This removes a simple possible obstruction but supplies no binary adjacency matrix.

A rooted partition with perfect matchings between cells.

Fix $x$, and label its $57$ neighbours $u_1,\ldots,u_{57}$. They form an independent set, because a triangle is forbidden. Every other vertex has a unique neighbour among them, because it has exactly one common neighbour with $x$. Let \[ V_i=N(u_i)\setminus\{x\}. \] Each cell has $56$ vertices, the cells are disjoint, and they cover the $3192$ vertices outside $\{x\}\cup N(x)$. A cell is independent: an edge inside it would form a triangle with $u_i$. A vertex of $V_i$ has no neighbour among $N(x)$ other than $u_i$, so it has exactly $56$ neighbours within the union of the cells.

It has at most one neighbour in any particular other cell $V_j$. Two such neighbours, together with $u_j$, would create a four-cycle and give the pair consisting of the vertex and $u_j$ two common neighbours. There are exactly $56$ other cells and $56$ neighbours to place, so it has exactly one neighbour in each other cell. Consequently every pair of distinct cells is joined by a perfect matching. This is forced by the Moore conditions, not an optional regularity assumption imposed to simplify a search.

The remaining permutation-matrix equations.

Let $C$ be the $3192$ by $3192$ adjacency matrix induced on the cells. Its diagonal $56$ by $56$ blocks are zero; each off-diagonal block is a permutation matrix, and opposite blocks are transposes. Let $K$ be the block-diagonal matrix consisting of $57$ copies of $J_{56}$. Counting common neighbours in the full graph gives the exact equation \[ C^2=56I+J-K-C. \] On the diagonal this says the degree is $56$. For distinct vertices in the same cell the right side is zero, since their one common neighbour is already $u_i$. For vertices in different cells the right side is zero when they are adjacent and one otherwise; their common neighbour cannot be in $N(x)$, so it must be counted by $C^2$.

Conversely, permutation blocks satisfying this equation recover the full Moore graph by adjoining the $u_i$ and $x$. The root and first layer have the prescribed degrees and common-neighbour counts by the matching rules. The equation supplies all remaining counts. Therefore one can seek a genuine solution of these equations without assuming that all matchings arise from one group action.

For three cells $i,j,k$, following matchings around the triangle of cells defines a permutation of $V_i$. It must have no fixed point, since a fixed point creates a triangle in the graph. This gives many necessary restrictions. Avoiding those fixed points individually is still insufficient: common-neighbour counts also constrain paths through pairs of intermediate cells. Assigning each matching locally without those global compatibility equations is the missing step in a naive permutation construction.

Cycle counts do not produce an integrality obstruction.

Choose two neighbours $u_i,u_j$ of $x$. There are $56$ matching edges between $V_i$ and $V_j$, and each gives a five-cycle through $x$. Every five-cycle through $x$ arises in this way. Hence there are $\binom{57}{2}56=57\cdot56^2/2$ such cycles through each vertex. Dividing the total over all vertices by five gives \[ \frac{3250\cdot57\cdot56^2}{10} =58094400 \] five-cycles. The count is integral and positive. It provides an exact check on a future construction, but not an existence theorem or a contradiction.

Executed analogue and limitations of symmetry arguments.

At degree three the same rooted structure has three cells of size two. The script constructs the Petersen graph from disjoint two-subsets of a five-element set, checks its $(10,3,0,1)$ common-neighbour counts, and verifies the perfect matching between every pair of rooted cells. This is a check that the deductions admit the known smaller model; no $3250$-vertex candidate was generated. The files checks_graphs.py and results_graphs.json are under _Local/Erdos_problems/UnsolvedMath/attempt_audit_2026_10_01/number_theory/.

A proof forbidding an automorphism of a specified order narrows the search only when existence of that automorphism has separately been proved. None is forced here. A graph with trivial automorphism group would evade every nontrivial-automorphism exclusion while satisfying the original problem's quantifiers.

Remaining gap and outcome.

The exact residual task is to construct compatible permutation blocks for $C$, or prove their simultaneous impossibility. Feasible spectrum, cycle counts, and all pairwise matching requirements leave that task open. Outcome: UNRESOLVED. No claimed nonexistence theorem from the imported source list is used as an unexamined premise.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1413 (GRAPH-026), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 V. Faber and J. Keegan, Existence of a Moore graph of degree 57 is still open, arXiv:2210.09577 $2022$. https://arxiv.org/abs/2210.09577. Bibliographic information from the supplied record.

• S3 Y. Ishida, No involutions in the missing Moore graph, arXiv:2606.29183 $2026$. https://arxiv.org/abs/2606.29183. Bibliographic information from the supplied record.

• S4 A. A. Makhnev, Moore graph with parameters $3250,57,0,1$ does not exist, arXiv:2010.13443 $2020$. https://arxiv.org/abs/2010.13443. Bibliographic information from the supplied record.

• E1 Vance Faber and James Keegan, Existence of a Moore graph of degree 57 is still open, arXiv:2210.09577v6. https://arxiv.org/abs/2210.09577v6. Primary version page inspected 1 October 2026.
• E2 Y. Ishida, No involutions in the missing Moore graph, arXiv:2606.29183v2. https://arxiv.org/abs/2606.29183v2. Primary version page inspected 1 October 2026. The automorphism restriction is distinguished from unrestricted nonexistence.