コンウェイの99グラフ問題

このようなパラメータを持つグラフが存在する可能性は、既に1969年にノーマン・L・ビッグス（英語版）によって示唆されており^[5]、またその存在が未解決問題であることがコンウェイ以前に他の著者によって記されている^[3][6][7][8]。コンウェイ自身はこの問題に 1975年から取り組み始めたが^[6]、賞金を提示したのは2014年、DIMACS Conference on Challenges of Identifying Integer Sequences において提示された問題群の一部としてであった。この問題群には thrackle（英語版）予想、ダンツァー集合（英語版）での間隙の最小値に関するもの、sylver coinage（英語版）ゲームで16手後にどちらのプレイヤーが勝つかを問う問題が含まれている^[1]。

より一般に、任意の辺がただ一つの三角形の1辺となり、任意の隣接しない2頂点がただ一つの四角形の向かい合う頂点となるような強正則グラフには、5通りのパラメータの組しか許されない。そのうち存在がわかっているのは2通りの組だけであり、頂点数が9のペイリーグラフ（英語版）（3-3 duoprism（英語版） のグラフ）はパラメータが (9,4,1,2) 、バーレカンプ–ヴァン・リント–ザイデルグラフはパラメータが (243,22,1,2) である。99グラフ問題は、5通りのパラメータの組の中で存在がわかっていないもののうち最小のものである^[4]。