Conway's 99-Graph Problem

Conway’s Ninety-Nine-Graph Problem

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.

Seek a simple graph with 99 vertices, every vertex of degree 14, every adjacent pair having exactly one common neighbour and every nonadjacent pair exactly two. These are the strongly regular parameters $(99,14,1,2)$; the graph is not specified up to any additional symmetry requirement. [S1] [S2]

Statement recorded in the supplied source.

Does there exist a strongly regular graph with parameters $99,14,1,2$? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Construct an srg$99,14,1,2$ or prove that the remaining locally and spectrally feasible structures cannot exist. [S1]

Short English statement

Is there a ninety-nine-vertex graph with degree fourteen and exactly the prescribed common-neighbour counts for adjacent and nonadjacent pairs?

Research attempt

Scope and status of the route.

The graph sought has no required automorphisms. The reduction here keeps that full scope by fixing a vertex, not a symmetry group. The primary record [E1] describes essentially this forced-neighbourhood route and explicitly leaves existence unresolved. Its second version lists both Aalok Thakkar and Simone Severini; the imported bibliography above records only the former. The derivations below are self-contained and are not asserted to be a new reduction.

Spectral feasibility does not exclude the parameters.

Counting length-two walks yields \[ A^2=12I-A+2J,\qquad A\mathbf1=14\mathbf1. \] The graph is connected, since any nonadjacent pair has two common neighbours. Thus the principal eigenvalue $14$ is simple. On $\mathbf1^\perp$, the eigenvalues solve $r^2+r-12=0$, so they are $3$ and $-4$. If their multiplicities are $f,g$, then \[ f+g=98,\qquad 14+3f-4g=0, \qquad (f,g)=(56,42). \] All multiplicities are nonnegative integers. Therefore the most direct spectral integrality test supplies no contradiction. It is invalid to replace the graph problem by finding a real symmetric matrix with these eigenvalues: the zero diagonal and binary entries are essential.

The first neighbourhood is forced.

Fix a vertex $x$, and let $U=N(x)$, with $|U|=14$. For $u\in U$, the neighbours of $u$ within $U$ are precisely the common neighbours of $u,x$, so there is exactly one. Hence the induced graph on $U$ is a matching of seven edges. Let $W$ be the remaining $84$ vertices. Each $w\in W$ is nonadjacent to $x$ and has exactly two neighbours in $U$. Those two cannot form a matched pair: such a pair already has $x$ as its unique common neighbour.

Conversely, two vertices $u,v\in U$ from different matched pairs are nonadjacent. They have $x$ as one common neighbour and no common neighbour inside $U$, because $U$ is a matching. Their second common neighbour is therefore a unique vertex of $W$. There are \[ \binom{14}{2}-7=84 \] such pairs. This establishes a bijection between $W$ and the unordered nonmatched pairs of $U$, not merely an upper bound on their number. Each $u\in U$ belongs to twelve pair labels, and each $w\in W$ has its remaining twelve neighbours within $W$.

Explicit residual integer equations.

Let $M$ be the $14$ by $14$ adjacency matrix of the matching. Let $B$ be the $14$ by $84$ incidence matrix of the nonmatched pairs: each column has two ones, and each row has twelve. All entries of $B$ are fixed after labeling the seven matched pairs. Its Gram matrix is \[ BB^T=11I+J-M. \] Indeed the diagonal is twelve; a matched pair of rows has intersection zero; all other pairs have intersection one. The full adjacency matrix must take the form \[ A=\begin{pmatrix} 0&\mathbf1^T&0\\ \mathbf1&M&B\\ 0&B^T&C \end{pmatrix}, \] where $C$ is symmetric, binary, has zero diagonal, and has row sum twelve. The remaining blocks of $A^2=12I-A+2J$ give \[ BC=2J-B-MB, \qquad C^2+B^TB=12I-C+2J. \] Here the all-ones matrices have the sizes dictated by the equations. Conversely any such $C$ produces the required full matrix: the root blocks follow from the column sums of $B$; the $U,U$ block follows from $M^2=I$ and the displayed formula for $BB^T$; the two remaining blocks are exactly these equations. Thus this is an equivalent finite feasibility problem, with no discarded asymmetric solutions.

The first residual equation has a direct interpretation. For each outside vertex and each member of $U$, it fixes how many neighbours of that outside vertex carry the member in their pair labels. The quadratic equation then enforces the common-neighbour counts inside $W$. Satisfying only the row sums and the first equation is not enough; those conditions do not determine $C^2$.

Additional counts and a model that checks the reduction.

There would be $99\cdot14/2=693$ edges. Each edge lies in a unique triangle, giving $231$ triangles. There are $\binom{99}{2}-693=4158$ nonedges. Each has two common neighbours, so it is a diagonal of a four-cycle. The common neighbours cannot be adjacent, since then that edge would have two common neighbours. Every such cycle is induced and is counted by its two diagonals, giving $2079$ induced four-cycles. These integral counts agree; they do not force incompatible incidence.

For an actual smaller instance, take the nine squares of a $3$ by $3$ board and join squares in the same row or column. Adjacent squares have one common neighbour and nonadjacent squares have two. At a fixed square its four neighbours induce two matched edges, and its four outside vertices correspond exactly to the four nonmatched pairs. The script checks every common-neighbour count and these four labels. This validates the combinatorial reduction on a genuine example, not the existence of its ninety-nine-vertex counterpart.

Verification record and remaining gap.

The exact small checks are in checks_graphs.py and results_graphs.json under _Local/Erdos_problems/UnsolvedMath/attempt_audit_2026_10_01/number_theory/. No exhaustive feasibility search on the $84$ by $84$ unknown matrix was run. In particular a partial-score adjacency matrix, a failed circulant search, or a restriction on possible automorphisms would not settle the unrestricted equations. A binary solution $C$ or a complete infeasibility certificate is the precise missing output. Outcome: UNRESOLVED.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1411 (GRAPH-024), 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 P. G. Cesarz and A. J. Woldar, On the automorphism group of a putative Conway 99-graph, Algebraic Combinatorics 8 $2025$, 379–398. https://doi.org/10.5802/alco.418. Bibliographic information from the supplied record.

• S3 A. Thakkar, A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph, arXiv:2608.11211 $2026$. https://arxiv.org/abs/2608.11211. Bibliographic information from the supplied record.

• E1 Aalok Thakkar and Simone Severini, A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph, arXiv:2608.11211v2, revised 18 September 2026. https://arxiv.org/abs/2608.11211v2. Primary abstract and version metadata inspected 1 October 2026. The reported search scores are partial constructions, not existence certificates.