Conway's 99-graph problem

概要

グラフ理論の未解決問題Conway's 99-graph problemを紹介する

$$$$

以下を満たす99頂点のgraph $G=(V,E)$は存在するか。
(1)任意の$e\in E$に対して$e$を含む3-cycleがただ一つする。
(2)任意の$e^\prime\in E^c$に対して$e^\prime$を対角線とする4-cycleがただ一つ存在する。
この問題をConway's 99-graph problemと呼ぶ。