コンウェイの99グラフ問題
コンウェイの99グラフ問題（コンウェイの99グラフもんだい、テンプレート:Lang-en-short）はグラフ理論の未解決問題の一つであり、次の性質を持つ99個の頂点からなる無向グラフが存在するかどうかを問う。
- 任意の隣接する2頂点がちょうど1個の共通の隣接頂点を持ち、任意の隣接しない2頂点がちょうど2個の共通の隣接頂点を持つ。同じことだが、任意の辺がただ一つの三角形の1辺となり、任意の隣接しない2頂点がただ一つの4-閉路の向かい合う2頂点となる。
ジョン・ホートン・コンウェイはこの問題の解決に対して1000ドルの賞金を提示しているテンプレート:R。
性質
もしそのようなグラフが存在すれば、必ずテンプレート:仮リンク（locally linear graph）で、パラメータ (99,14,1,2) の強正則グラフである。1、3、4番目のパラメータはこの問題の条件をコード化したもので、グラフの頂点数が99個であること、どの隣接する2頂点もちょうど1個の共通する隣接頂点を持つこと、どの隣接しない2頂点もちょうど2個の共通する隣接頂点を持つこと、を表している。2番目のパラメータはグラフが14-正則グラフであることを表しているテンプレート:R。
もしこのようなグラフが存在すれば、それには位数11の対称性（グラフの自己同型）は存在せず、したがって任意の頂点が任意の頂点へ写るような対称性は持たないことがわかっているテンプレート:R。対称性に関してはこれ以外にも制約が課されねばならないことが知られているテンプレート:R。
歴史
このようなパラメータを持つグラフが存在する可能性は、既に1969年にテンプレート:仮リンクによって示唆されておりテンプレート:R、またその存在が未解決問題であることがコンウェイ以前に他の著者によって記されているテンプレート:R。コンウェイ自身はこの問題に 1975年から取り組み始めたがテンプレート:R、賞金を提示したのは2014年、DIMACS Conference on Challenges of Identifying Integer Sequences において提示された問題群の一部としてであった。この問題群には テンプレート:Ill2予想、テンプレート:仮リンクでの間隙の最小値に関するもの、テンプレート:Ill2ゲームで16手後にどちらのプレイヤーが勝つかを問う問題が含まれているテンプレート:R。
関連するグラフ
より一般に、任意の辺がただ一つの三角形の1辺となり、任意の隣接しない2頂点がただ一つの四角形の向かい合う頂点となるような強正則グラフには、5通りのパラメータの組しか許されない。そのうち存在がわかっているのは2通りの組だけであり、頂点数が9のテンプレート:仮リンク（テンプレート:Ill2 のグラフ）はパラメータが (9,4,1,2) 、バーレカンプ–ヴァン・リント–ザイデルグラフはパラメータが (243,22,1,2) である。99グラフ問題は、5通りのパラメータの組の中で存在がわかっていないもののうち最小のものであるテンプレート:R。