Graph theory · Open problem

The graph with 99 vertices.

Conway asked whether a graph with strict neighbor counts could exist. The existence question remains open.

Illustrated rook grid representing a local graph pattern
Local patterns in Conway's graph problem

Conway's question

Does there exist a simple graph with 99 vertices in which every vertex has degree 14, adjacent vertices share exactly one neighbor, and nonadjacent vertices share exactly two? These are the parameters of a strongly regular graph (99, 14, 1, 2).

Structural results

The unrefereed research repository records arguments, certificates and construction searches. One result gives an upper bound of 120 induced 3 × 3 rook grids, compared with an earlier published bound of 231. The supporting grid-intersection notes explain the statement and scope.

Additional notes study independent sets and eigenlattice constraints. These remain partial necessary conditions rather than a construction or nonexistence proof.

Try the neighbor rule

The homepage rook-graph experiment lets you select two positions and compare their common neighbors. It is a nine-vertex teaching example with four neighbors per vertex, not a proposed solution of the 99-vertex problem.

The existence question is unsolved. These results are unrefereed and do not resolve it.

Reproduce or inspect