graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, Conway's 99-graph problem is an unsolved problem asking whether there exists an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

with 99 vertices, in which each two adjacent vertices have exactly one common neighbor, and in which each two non-adjacent vertices have exactly two common neighbors. Equivalently, every edge should be part of a unique triangle and every non-adjacent pair should be one of the two diagonals of a unique 4-cycle.

John Horton Conway John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches ...

offered a $1000 prize for its solution.

Properties

If such a graph exists, it would necessarily be a

locally linear graph In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be ...

and a

strongly regular graph In graph theory, a strongly regular graph (SRG) is defined as follows. Let be a regular graph with vertices and degree . is said to be strongly regular if there are also integers and such that: * Every two adjacent vertices have commo ...

with parameters (99,14,1,2). The first, third, and fourth parameters encode the statement of the problem: the graph should have 99 vertices, every pair of adjacent vertices should have 1 common neighbor, and every pair of non-adjacent vertices should have 2 common neighbors. The second parameter means that the graph is a

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...

with 14 edges per vertex. If this graph exists, it cannot have symmetries that take every vertex to every other vertex. Additional restrictions on its possible groups of symmetries are known.

History

The possibility of a graph with these parameters was already suggested in 1969 by Norman L. Biggs, and its existence noted as an open problem by others before Conway. Conway himself had worked on the problem as early as 1975, but offered the prize in 2014 as part of a set of problems posed in the DIMACS Conference on Challenges of Identifying Integer Sequences. Other problems in the set include the thrackle conjecture, the minimum spacing of

Danzer set In geometry, a Danzer set is a set of points that touches every convex body of unit volume. Ludwig Danzer asked whether it is possible for such a set to have bounded density. Several variations of this problem remain unsolved. Density One way t ...

s, and the question of who wins after the move 16 in the game sylver coinage.

Related graphs

More generally, there are only five possible combinations of parameters for which a strongly regular graph could exist with each edge in a unique triangle and each non-edge forming the diagonal of a unique quadrilateral. It is only known that graphs exist with two of these five combinations. These two graphs are the nine-vertex

Paley graph In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, ...

(the graph of the

3-3 duoprism In the geometry of 4 dimensions, the 3-3 duoprism or triangular duoprism is a 4-polytope, four-dimensional convex polytope. It can be constructed as the Cartesian product of two triangles and is the simplest of an infinite family of four-dimensiona ...

) with parameters (9,4,1,2) and the

Berlekamp–van Lint–Seidel graph In graph theory, the Berlekamp–Van Lint–Seidel graph is a locally linear strongly regular graph with parameters (243,22,1,2). This means that it has 243 vertices, 22 edges per vertex (for a total of 2673 edges), exactly one shared neighbor per ...

with parameters (243,22,1,2). The parameters for which graphs are unknown are: (99,14,1,2), (6273,112,1,2) and (494019,994,1,2). The 99-graph problem describes the smallest of these combinations of parameters for which the existence of a graph is unknown.

References

{{reflist, refs= {{citation , last = Biggs , first = Norman , authorlink = Norman L. Biggs , mr = 0327563 , page = 111 , publisher = Cambridge University Press , location = London and New York , series = London Mathematical Society Lecture Note Series , title = Finite Groups of Automorphisms: Course Given at the University of Southampton, October–December 1969 , url = https://books.google.com/books?id=flA4AAAAIAAJ&pg=PA111 , volume = 6 , year = 1971, isbn = 9780521082150 {{citation , last1 = Behbahani , first1 = Majid , last2 = Lam , first2 = Clement , doi = 10.1016/j.disc.2010.10.005 , issue = 2-3 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

, mr = 2739917 , pages = 132–144 , title = Strongly regular graphs with non-trivial automorphisms , volume = 311 , year = 2011, doi-access = free {{citation , last1 = Brouwer , first1 = A. E. , author1-link = Andries Brouwer , last2 = Neumaier , first2 = A. , doi = 10.1007/BF02122552 , issue = 1 , journal = Combinatorica , mr = 951993 , pages = 57–61 , title = A remark on partial linear spaces of girth 5 with an application to strongly regular graphs , volume = 8 , year = 1988, s2cid = 206812356 , url = https://ir.cwi.nl/pub/1721 {{citation , last = Cameron , first = Peter J. , authorlink = Peter Cameron (mathematician) , isbn = 0-521-45133-7 , mr = 1311922 , page = 331 , publisher = Cambridge University Press , location = Cambridge , title = Combinatorics: topics, techniques, algorithms , url = https://books.google.com/books?id=_aJIKWcifDwC&pg=PA331 , year = 1994 {{citation , last = Conway , first = John H. , author-link = John Horton Conway , accessdate = 2019-02-12 , publisher =

On-Line Encyclopedia of Integer Sequences The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...

, title = Five $1,000 Problems (Update 2017) , url = https://oeis.org/A248380/a248380.pdf. See also {{OEIS el, A248380. {{citation , last = Guy , first = Richard K. , authorlink = Richard K. Guy , editor-last = Kelly , editor-first = L. M. , editor-link = Leroy Milton Kelly , contribution = Problems , doi = 10.1007/BFb0081147 , location = Berlin and New York , mr = 0388240 , pages = 233–244 , publisher = Springer-Verlag , series = Lecture Notes in Mathematics , title = Proceedings of a Conference held at Michigan State University, East Lansing, Mich., June 17–19, 1974 , volume = 490 , year = 1975. See problem 7 (J. J. Seidel), pp. 237–238. {{citation , last1 = Makhnev , first1 = A. A. , last2 = Minakova , first2 = I. M. , date = January 2004 , doi = 10.1515/156939204872374 , issue = 2 , journal = Discrete Mathematics and Applications , mr = 2069991 , title = On automorphisms of strongly regular graphs with parameters

\lambda=1

\mu=2

, volume = 14, s2cid = 118034273 {{citation , last = Wilbrink , first = H. A. , editor1-last = de Doelder , editor1-first = P. J. , editor2-last = de Graaf , editor2-first = de, J. , editor3-last = van Lint , editor3-first = J. H. , contribution = On the (99,14,1,2) strongly regular graph , date = August 1984 , pages = 342–355 , publisher = Eindhoven University of Technology , series = EUT Report , title = Papers dedicated to J. J. Seidel , url = https://research.tue.nl/files/2449333/256699.pdf , volume = 84-WSK-03 {{citation , last1 = Zehavi , first1 = Sa'ar , last2 = David de Olivera , first2 = Ivo Fagundes , arxiv = 1707.08047 , title = Not Conway's 99-graph problem , year = 2017 Strongly regular graphs Unsolved problems in graph theory John Horton Conway