57-regular Moore graph?

57-regular Moore graph?

Definitions and mathematical statement

Consider finite simple undirected graphs. The degree of a vertex is its number of neighbours, and a graph is $57$-regular when every vertex has degree $57$. In a connected graph the distance between two vertices is the minimum number of edges in a joining path; the diameter is the maximum of these distances. The girth is the length of a shortest simple cycle.

The existence question asks whether there is a $57$-regular graph $G$ of diameter two and girth five. Thus any two distinct vertices must either be adjacent or have a common neighbour, while triangles and quadrilaterals are forbidden. Equivalently, one seeks a strongly regular graph with parameters \[ (v,k,\lambda,\mu)=(3250,57,0,1): \] there are $3250$ vertices, each has $57$ neighbours, adjacent vertices have no common neighbour, and nonadjacent vertices have exactly one common neighbour.

The order $3250$ follows by exploring distances from any vertex: there are $1$ vertex at distance zero, $57$ at distance one, and $57\cdot56$ distinct vertices at distance two. Girth five prevents overlaps in that exploration, and diameter two exhausts the graph. Hence the problem is a finite existence question at a prescribed order, not a request for arbitrarily large graphs. Either an explicit construction with the stated properties or a proof that the parameter conditions are impossible would answer it.

Short English statement

Does a graph on 3250 vertices exist in which each vertex has 57 neighbours, adjacent pairs share none, and nonadjacent pairs share exactly one?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Literature and attack plan.

The parameter set in [S2] is the missing degree-$57$ Moore graph. A June 2026 preprint by Ishida [R1] studies restrictions on its hypothetical automorphisms; its abstract claims that no involution can occur. That claim is not used here, and excluding particular symmetries would not exclude a graph with trivial automorphism group. Our plan is instead to extract exact spectral restrictions and an equivalent system of permutation-matrix equations, then check the reduction in degree three.

Spectral restrictions and a quantitative consequence.

Let $A$ be the adjacency matrix of a putative graph and $J$ the all-one matrix. Counting common neighbours gives \[ A^2=56I-A+J. \] The graph is connected, so its regular eigenvalue $57$ has multiplicity one. On the orthogonal complement of the all-one vector, the remaining eigenvalues satisfy $t^2+t-56=0$, and hence are $7$ and $-8$. Writing their multiplicities as $f,g$, dimension and trace give \[ f+g=3249,\qquad 57+7f-8g=0, \qquad(f,g)=(1729,1520). \] Both multiplicities are positive integers; the spectral feasibility test therefore supplies no contradiction.

There is nevertheless a useful restriction on independent sets. If $S$ is independent with size $a$, put $z=1_S-(a/3250)1$. Then $z^TAz=-57a^2/3250$ and $z^Tz=a-a^2/3250$. The lower eigenvalue bound $z^TAz\ge-8z^Tz$ yields $a\le400$. If $a=400$, equality forces $Az=-8z$, so every vertex outside $S$ has precisely eight neighbours in $S$. Thus even an extremal independent set would impose a regular incidence structure rather than immediately contradicting the parameters.

An exact local-to-global matrix system.

Fix a vertex $v$ and enumerate its neighbours $u_1,\ldots,u_{57}$. For each $i$, let $B_i=N(u_i)\setminus\{v\}$. Girth five makes these $57$ sets disjoint, independent, and of size $56$. They exhaust all remaining vertices. A vertex $x\in B_i$ has exactly one neighbour in each $B_j$ with $j\ne i$: the nonadjacent pair $x,u_j$ has exactly one common neighbour, which must lie in $B_j$. The edges between $B_i,B_j$ are consequently a perfect matching.

After labelling each block by $\{1,\ldots,56\}$, let $P_{ij}$ be its matching matrix, with rows indexed by $B_i$ and columns by $B_j$. Then $P_{ji}=P_{ij}^{T}$ and each $P_{ij}$ is a permutation matrix. For distinct $i,j$, counting common neighbours of vertices in these two blocks gives the entrywise equation \[ \boxed{\ \sum_{h\ne i,j}P_{ih}P_{hj}=J_{56}-P_{ij}.\ } \] There are $55$ summands. A matched pair has no common neighbour, while every unmatched pair has one. These common neighbours can only occur in the other blocks.

Conversely, suppose permutation matrices satisfying all these equations exist. Add vertices $v,u_1,\ldots,u_{57}$ to the blocks, join $v$ to all $u_i$, join $u_i$ to its entire block, and insert the specified matchings. Every vertex has degree $57$. Two distinct vertices within one block have their common neighbour $u_i$ and no other, since each interblock matching is bijective. Pairs in different blocks have the required common-neighbour count by the displayed equation. The remaining pair types, involving $v$ or a vertex $u_i$, have counts zero when adjacent and one otherwise, directly from the construction. This proves that the matrix system is equivalent to the original existence problem. It is a reduction, not a construction of its required solution.

Verification and first obstruction.

For the degree-three analogue there are three blocks of size two. Set $P_{12}=P_{13}=I_2$ and $P_{23}=J_2-I_2$, with reverse matrices their transposes. Every equation holds. The resulting ten-vertex graph has adjacency identity $A^2=2I-A+J$ and is a Petersen graph. The reproducible script scripts/check_attempt_batch02_algebra_2026_10_01.py checks every pair's degree and common-neighbour conditions for this small construction. This validates the indices and diagonal exclusions in the reduction; it supplies no evidence that the $56$-point system is feasible.

Final status.

UNRESOLVED. The spectral data are consistent, and the exact permutation constraints retain all the difficulty. The first missing step is either a family of $57$ mutually compatible matching systems satisfying these equations, or a contradiction valid for every such family without an unjustified symmetry assumption.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3143 (OPG-160), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, 57-regular Moore graph?. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/57_regular_moore_graph.

• R1 Yawara Ishida, No involutions in the missing Moore graph, 2026, arXiv v2 dated 8 July 2026. Primary preprint abstract checked 1 October 2026; its automorphism claim is not used as a lemma. https://arxiv.org/abs/2606.29183.