Conway's 99-graph problem

Is there a graph on 99 vertices in which every edge lies in exactly one triangle and every two non-adjacent vertices are opposite corners of exactly one four-cycle? John Conway offered 1000 US dollars for an answer either way. The parameters pass every known feasibility test, and a candidate graph would be checked in milliseconds.

Problem

A strongly regular graph with parameters $(v, k, \lambda, \mu)$ is a $k$-regular graph on $v$ vertices in which adjacent vertices have exactly $\lambda$ common neighbours and non-adjacent vertices exactly $\mu$. Equivalently, its adjacency matrix $A$ satisfies

$$A^2 = k I + \lambda A + \mu (J - I - A).$$

Question: does a strongly regular graph with parameters $(99, 14, 1, 2)$ exist? The condition $\lambda = 1$ says that every edge lies in a unique triangle, and $\mu = 2$ that every non-adjacent pair is the diagonal of a unique quadrilateral; $k = 14$ then follows from $v = 99$. Its eigenvalues would be $14$, $3$ (multiplicity 54) and $-4$ (multiplicity 44).

Background

Conway included the question among his "five $1,000 problems" in 2014. Graphs with $\lambda = 1$ and $\mu = 2$ are rare: the first example is the $3 \times 3$ rook's graph on 9 vertices, the product of two triangles. In Brouwer's table of strongly regular graphs, $(99, 14, 1, 2)$ is one of the two smallest parameter sets whose existence is still unknown. The automorphism group of a 99-graph would have to be small, so constructions that start from a large symmetry group cannot work.

What is known

• Status: open in Brouwer's table as of October 2026.
• Automorphisms: Makhnev and Minakova (2004) restricted the possible automorphisms. Cesarz and Woldar (2025) gave computer-free proofs that if the order of the automorphism group is even it divides 6, so the group is $\mathbb{Z}_2$, $\mathbb{Z}_6$ or $S_3$, and that if it is divisible by 7 the group is cyclic of order 7.
• Computational reductions: fixing one vertex forces its neighbourhood to be a perfect matching and determines its edges to the other 84 vertices, leaving a constrained 12-regular graph on 84 vertices; Thakkar and Severini (2026) encoded this in a constraint solver and showed that no circulant graph on 99 vertices comes close to satisfying the conditions.

What would count as progress

• A 99-graph, given as an edge list. Checking the matrix identity above takes milliseconds.
• A proof of nonexistence: a hand-checkable argument, or an exhaustive search (for example a SAT or constraint-programming formulation of the 84-vertex reduction) with certificates that can be checked independently.
• Further restrictions on the automorphism group, or nonexistence under a prescribed automorphism of order 3 or 11, which narrows the search.
• A Lean statement of the question is in formal-conjectures.

References

1. J. H. Conway, "Five $1,000 problems (update 2017)", OEIS, 2014–2017. PDF
2. A. A. Makhnev and I. M. Minakova, "On automorphisms of strongly regular graphs with parameters λ = 1, μ = 2", Discrete Mathematics and Applications 14 (2004). doi:10.1515/156939204872374
3. P. G. Cesarz and A. J. Woldar, "On the automorphism group of a putative Conway 99-graph", Algebraic Combinatorics 8 (2025), 379–398. doi:10.5802/alco.418
4. A. Thakkar and S. Severini, "A forced-structure reduction and verifiable bounds for Conway's 99-graph" (2026). arXiv:2608.11211

Source

Imported from Parameters of strongly regular graphs (A. E. Brouwer), 51–100 vertices, curated by Andries E. Brouwer. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.