動画の補足

このnoteはコンウェイの99頂点グラフ問題に関する動画(niconico/Youtube)の補足です.
コメントに質問などあれば加筆していきます.

定義

有限かつ空でない集合$${V}$$と異なる2元からなる$${V}$$の部分集合を元に持つ集合$${E}$$の組$${G=(V,E)}$$を単純無向グラフという.
この記事では単純無向グラフを単にグラフと呼ぶ.
また, $${V}$$の元を頂点, $${E}$$の元を辺と呼ぶ.

グラフ$${G=(V,E)}$$に対して, グラフ$${\overline{G}=(V,E^c)}$$を$${G}$$の補グラフと呼ぶ.

グラフ$${G=(V,E)}$$の2頂点$${u,v}$$に対して$${\{u,v\}\in E}$$ならば$${u,v}$$は隣接であるという.
そうでないとき, $${u,v}$$は非隣接であるという.

コンウェイの99頂点グラフ問題
(Conway's 99-graph problem)

以下の条件$${(T)(Q)}$$を満たす99頂点のグラフ$${G}$$が存在するか？
$${(T):}$$任意の隣接頂点$${u,v}$$に対して, 頂点$${w}$$が存在して$${\{u,w\},\{v,w\}\in E}$$が成り立つ
$${(Q):}$$任意の非隣接頂点$${u,v}$$に対して, 頂点$${x,y}$$が存在して$${\{u,x\},\{u,y\},\{x,v\},\{y,v\}\in E}$$

偽コンウェイの99頂点グラフ問題
(Not Conway's 99-graph problem)

以下の条件$${(T)(Q)}$$を満たす99頂点のグラフ$${G}$$が存在するか？
$${(T):}$$任意の隣接頂点$${u,v}$$に対して, 頂点$${w}$$が存在して$${\{u,w\},\{v,w\}\in E}$$が成り立つ
$${(Q^\prime):}$$任意の非隣接頂点$${u,v}$$に対して, 頂点$${x,y,z}$$が存在して$${\{u,x\},\{x,y\},\{y,v\}\in E^c}$$

証明の補足

(1)の3辺が異なる四角形に含まれる場合において追加される頂点が異なる理由
例えば$${G=D}$$を仮定すると, 辺$${DB}$$は2つの四角形$${AFDB}$$と$${BDEC}$$にともに含まれるので$${(Q^\p)}$$と矛盾する.
よって, 他も同じように証明することができるので追加された各頂点は異なる.

参考文献リスト

Not Conway's 99-Graph Problem
動画の元ネタ.
偽コンウェイについて証明が載っている.短くまとまっていて読みやすいのでおすすめ.