四色定理
四色定理(よんしょくていり、Four Color Theorem)
グラフ理論だと「平面グラフは4彩色可能である」という言い換えができるらしい
グラフ色分け問題
CoqでGeorges GonthierとBenjamin Wernerによって2004に証明が完了した
Coqでの証明
GitHub:
coq-community/fourcolor: Formal proof of the Four Color Theorem 【maintainer=@ybertot】
Haskellでの証明
righ1113/4CT_Haskell: 四色定理を Haskell に移植したよ（復活）
メモ
Georges Gonthier. A computer-checked proof of the Four Colour Theorem Georges Gonthier.
https://www.cse.chalmers.se/~abela/lehre/WS05-06/CAFR/4colproof.pdf
#Coq
#グラフ理論