離散数学講義スライド（四色定理）
3.2K Views
July 25, 24
スライド概要
離散数学の授業で使用＆配布した講義スライドです。
・四色問題の概説
・六色定理
・五色定理
・四色定理のケンプの誤証明
関連スライド
各ページのテキスト
四色問題 の概説
Four-Color Problem 四色問題 平面上のどんな地図も ４色あれば塗り分けられるか？ ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
Four-Color Problem 四色問題 平面上のどんな地図も ４色あれば塗り分けられるか？ ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
2色必要な平面地図 ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
2色必要な平面地図 ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
３色必要な平面地図 ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
３色必要な平面地図 ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
４色必要な平面地図 ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
４色必要な平面地図 ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
５色必要な平面地図？？ ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
５色必要な平面地図？？ ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
５色必要な平面地図？？ ３色で必要十分 ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
５色必要な平面地図は無いのか？ どれだけ意地悪に描いても4色で足りるの？
四色問題の発祥 1852年 Francis Guthrie フランシス・ガスリー Frederick Guthrie フレデリック・ガスリー Augustus de Morgan ド・モルガン William Rowan Hamilton ハミルトン
四色問題の解決の歴史 Augustus de Morgan ド・モルガン Arthur Cayley ケイリー 1878年 ロンドン数学会 Alfred Bray Kempe 187９年 ケンプが証明した・・・？ Kempe, A. B.; On the Geographical Problem of the Four Colours. Amer. J. Math. 2 (1879), no. 3, 193–200.
四色問題の解決の歴史 Alfred Bray Kempe 187９年 ケンプが証明した・・・？ Percy John Heawood 1890年 ヘイウッドが誤りを指摘 Heawood, P. J.; Map-colour theorem. The Quarterly Journal of Pure and Applied Mathematics 24 (1890), 332-338. 五色定理を証明 平面上のどんな地図も ５色あれば塗り分けられる
四色問題の解決の歴史 Alfred Bray Kempe 187９年 ケンプが証明した・・・？ Percy John Heawood 1890年 ヘイウッドが誤りを指摘 Heawood, P. J.; Map-colour theorem. The Quarterly Journal of Pure and Applied Mathematics 24 (1890), 332-338. 五色定理を証明 数学者たちの執念 ケンプの証明方針を発展 Kenneth Appel Wolfgang Haken 1977年 アッペルとハーケンが証明
アッペルとハーケンの論文 Appel, Kenneth; Haken, Wolfgang; Every Planar Map is Four Colorable. I. Discharging. Illinois Journal of Mathematics 21 (1977), no.3, 429-490. Appel, Kenneth; Haken, Wolfgang; Koch, John; Every Planar Map is Four Colorable. II. Reducibility. Illinois Journal of Mathematics 21 (1977), no.3, 491-567. 最終的に741ページの 単行本を出版 Appel, Kenneth; Haken, Wolfgang; Every Planar Map is Four-Colorable. Contemporary Mathematics 98 (1989).
最強コンビ アッペルとハーケンの論文 コンピュータに詳しい 四色問題に詳しい 487の規則を採用した手続きで 1834個（最終的に1405個まで減った） のパターンを見つける 全てのパターンが特定の条件を満たすことを 膨大な場合分けで証明する コンピュータ を使って証明した
物議を醸した 証明とは？ つまらない 証明の正しさを どう検証する？ 四色問題にしか 使えない証明法だ コンピュータが正しく 動作しなかったら？ エレガントじゃない エレファントな証明
物議を醸した 証明とは？ つまらない 証明の正しさを どう検証する？ 四色問題にしか 使えない証明法だ コンピュータが正しく 動作しなかったら？ エレガントじゃない 性能が向上したコンピュータで機械的に検証 人間には長すぎる証明しかない定理も 研究対象になる時代へ
アッペルとハーケンの論文以後 1997年 Robertsonらの新証明 • 証明方針は同じ＆コンピュータで証明 • 32個の規則、633個のパターン Robertson, Neil; Sanders, Daniel; Seymour, Paul; Thomas, Robin; The four-colour theorem. J. Combin. Theory Ser. B 70 (1997), no. 1, 2–44. 2008年 Gonthierの検証 • 証明支援システムCoqで検証完了 Gonthier, Georges; Formal proof—the four-color theorem. Notices Amer. Math. Soc. 55 (2008), no. 11, 1382–1393. 1997年～2017年 • Hales（ヘイルズ）によるケプラー予想の解決 • 証明支援システムで検証完了 Hales, Thomas; Adams, Mark; Bauer, Gertrud; Dang, Tat Dat; Harrison, John; Le Truong Hoang; Kaliszyk, Cezary; Magron, Victor; McLaughlin, Sean; Nguyen, Tat Thang; Nguyen, Quang Truong; Nipkow, Tobias; Obua, Steven; Pleso, Joseph; Rute, Jason; Solovyev, Alexey; Ta, Thi Hoai An; Tran, Nam Trung; Trieu, Thi Diep; Urban, Josef; Vu, Ky; Zumkeller, Roland A formal proof of the Kepler conjecture. Forum Math. Pi 5 (2017), e2, 29 pp.
参考文献 Wilson, Robin J.; Four Colours Suffice: How the Map Problem Was Solved. Penguin Books, (2003). ロビン・ウィルソン (著); 茂木健一郎 (翻訳); 四色問題. 新潮社, (2004). 一松信; 四色問題 どう解かれ何をもたらしたのか. 講談社, (2016). Biggs, Norman L.; Lloyd, E. Keith; Wilson, Robin J. Graph theory 1736–1936. Oxford University Press (1986). N.L. ビッグス (著); E.K. ロイド (著); R.J. ウィルソン (著); 一松信 (翻訳); 秋山仁 (翻訳); 恵羅博 (翻訳); グラフ理論への道. 地人書館, (1986).
六色定理
The Four-Color Theorem 四色定理 平面上のどんな地図も ４色あれば塗り分けられる ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
グラフでモデル化して塗り分けよう 地図の領域の形状はそれほど重要ではない どの異なる２つの領域が隣接しているかが重要
グラフでモデル化して塗り分けよう 地図の各領域をグラフの頂点とみなす
グラフでモデル化して塗り分けよう 異なる2つの領域が隣接しているとき 対応する２つの頂点を１つの辺で結ぶ
グラフでモデル化して塗り分けよう 辺同士が交差しないように平面上に描くと （単純）平面グラフを得る
グラフでモデル化して塗り分けよう 辺で結ばれた異なる2頂点は色が異なるように 各頂点を塗る 2 1 1 2 3 4 4 2 2 2 3 1 1 4 3 4
グラフでモデル化して塗り分けよう もとの地図の領域を 対応する頂点の色で塗る 2 1 1 2 3 4 4 2 2 2 3 1 1 4 3 4
グラフでモデル化して塗り分けよう もとの地図の領域が塗り分けられる
四色定理（頂点塗り分けVer.） 平面グラフの頂点は 4色以下で塗り分けられる 2 1 1 2 3 4 4 2 2 2 3 1 1 4 3 4
六色定理（頂点塗り分けVer.） 平面グラフの頂点は ６色以下で塗り分けられる 2 5 1 2 3 4 4 2 6 2 3 1 1 4 3 5
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. Gを平面グラフとする Gの頂点数nに関する数学的帰納法で証明する n=1のとき 1 1色で塗り分けられる n≧2のとき 頂点数がn-1の平面グラフの頂点は 6色以下で塗り分けられると仮定する
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が0の頂点 v が存在するとき G-v は n-1 頂点の平面グラフ 帰納法の仮定よりG-vは6色以下で塗り分けられる v G-v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が0の頂点 v が存在するとき G-ｖ を6色以下で塗り分ける v を適切に塗ればGは6色以下で塗り分けられる v 1 6色以下で塗り分け G-v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が1の頂点 v が存在するとき G-v は n-1 頂点の平面グラフ 帰納法の仮定よりG-vは6色以下で塗り分けられる v G-v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が1の頂点 v が存在するとき G-ｖ を6色以下で塗り分ける v の次数は1だから塗れる色が5色余っている v 1 6色以下で塗り分け G-v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が1の頂点 v が存在するとき 余っている色でvを塗る Gは6色以下で塗り分けられる v 1 6色以下で塗り分け G-v 2
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が2の頂点 v が存在するとき G-v は n-1 頂点の平面グラフ 帰納法の仮定よりG-vは6色以下で塗り分けられる v G-v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が2の頂点 v が存在するとき G-ｖ を6色以下で塗り分ける v の次数は2だから塗れる色が4色余っている 2 1 6色以下で塗り分け G-v v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が2の頂点 v が存在するとき 余っている色でvを塗る Gは6色以下で塗り分けられる 2 1 6色以下で塗り分け G-v v 3
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が3の頂点 v が存在するとき G-v は n-1 頂点の平面グラフ 帰納法の仮定よりG-vは6色以下で塗り分けられる v G-v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が3の頂点 v が存在するとき G-ｖ を6色以下で塗り分ける v の次数は3だから塗れる色が3色余っている 2 1 3 6色以下で塗り分け G-v v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が3の頂点 v が存在するとき 余っている色でvを塗る Gは6色以下で塗り分けられる 2 1 4 3 6色以下で塗り分け G-v v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が4の頂点 v が存在するとき G-v は n-1 頂点の平面グラフ 帰納法の仮定よりG-vは6色以下で塗り分けられる v G-v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が4の頂点 v が存在するとき G-ｖ を6色以下で塗り分ける v の次数は4だから塗れる色が2色余っている 4 2 1 3 6色以下で塗り分け G-v v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が4の頂点 v が存在するとき 余っている色でvを塗る Gは6色以下で塗り分けられる 4 2 1 5 3 6色以下で塗り分け G-v v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が5の頂点 v が存在するとき G-v は n-1 頂点の平面グラフ 帰納法の仮定よりG-vは6色以下で塗り分けられる v G-v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が5の頂点 v が存在するとき G-ｖ を6色以下で塗り分ける v の次数は5だから塗れる色が1色余っている 4 v 2 1 3 5 6色以下で塗り分け G-v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が5の頂点 v が存在するとき 余っている色でvを塗る Gは6色以下で塗り分けられる 4 v 2 1 6 3 5 6色以下で塗り分け G-v
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が5以下の頂点が存在するとき Gは6色以下で塗り分けられる 次数が5以下の頂点が存在しないとき 五辺国補題より そのような場合はありえない
五辺国補題 平面グラフには次数が5以下の頂点がある 五辺国
五辺国補題 平面グラフには次数が5以下の頂点がある 非平面グラフ 気持ち 平面グラフ 交差しないように描こうとすると 辺をたくさんは描けないよね
五辺国補題の証明 連結な平面グラフについて証明すればよい Gを連結な平面グラフとする 頂点数が6以下のとき どの頂点も次数は5以下である 頂点数が7以上のとき 非連結な平面グラフは 複数の連結な平面グラフ から構成されるので それぞれに次数5以下の 頂点がある 辺の数を数えてみよう 気持ち 交差しないように描こうとすると 辺をたくさんは描けないよね
五辺国補題の証明 Gは、平面をいくつかの閉じた領域と １つの開いた領域に分割する n : 頂点数 m : 辺数 r : 領域数 とおく n≧7≧4、また、Gは連結な単純グラフなので どの領域の境界も3本以上の辺を含む n<4 非連結 単純でない n≧4＆単純連結
五辺国補題の証明 Gの各辺の両サイドに1個ずつアメ アメの総数を数えてみよう を置く
五辺国補題の証明 どの領域の境界も3本以上の辺を含むので どの領域にもアメは３個以上ある アメの総数 ≧ 3r アメは辺１本ごとに2個ずつ置いているので アメの総数 ＝ 2m ゆえに 3r ≦ 2m
五辺国補題の証明 平面グラフのオイラーの公式より 2 = r-m+n 連結な平面グラフの 領域、辺、頂点の数を それぞれ r 、m、nとおくと 6 = 3r-3m+3n r-m+n = 2 ≦ 2m-3m+3n ≦ -m+3n m ≦ 3n-6 辺がたくさんは無い
五辺国補題の証明 握手補題より 単純グラフの次数の総和は 辺の数の2倍である Gの次数の総和 = 2m ≦ 6n-12 < 6n よってGには次数が5以下の頂点が存在する よって五辺国補題は成り立つ
六色定理（頂点塗り分けVer.）の証明 数学的帰納法Ver. 次数が5以下の頂点が存在するとき Gは6色以下で塗り分けられる 次数が5以下の頂点が存在しないとき 五辺国補題より そのような場合はありえない よってGは6色以下で塗り分けられる 以上より、六色定理は成り立つ
六色定理（頂点塗り分けVer.） 平面グラフの頂点は ６色以下で塗り分けられる 2 5 1 2 3 4 4 2 6 2 3 1 1 4 3 5
六色定理（頂点塗り分けVer.）の証明 背理法Ver. 背理法で証明する 背理法の仮定 6色以下では塗り分けできない平面グラフがある 6色以下では塗り分けできない平面グラフのうち 頂点数が最小のものをひとつ選び G とおく 最小反例 五辺国補題よりGには次数が5以下の頂点がある 次数が5以下の頂点をひとつ選び v とおく
六色定理（頂点塗り分けVer.）の証明 背理法Ver. G-v は G より頂点数が少ない平面グラフ Gは最小反例だからG-vは6色以下で塗り分けられる v 次数５以下 G-v
六色定理（頂点塗り分けVer.）の証明 背理法Ver. G-ｖ を6色以下で塗り分ける v の次数は6より小さいから塗れる色が余っている 4 v 2 1 3 次数５以下 5 G-v
六色定理（頂点塗り分けVer.）の証明 背理法Ver. 余っている色でvを塗る Gは6色以下で塗り分けられる Gの定義に矛盾するため定理は成り立つ 4 v 2 1 6 3 次数５以下 5 G-v
六色定理（頂点塗り分けVer.） 平面グラフの頂点は ６色以下で塗り分けられる 2 5 1 2 3 4 4 2 6 2 3 1 1 4 3 5
五色定理
The Four-Color Theorem 四色定理 平面上のどんな地図も ４色あれば塗り分けられる ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
グラフでモデル化して塗り分けよう 地図を(単純)平面グラフでモデル化
グラフでモデル化して塗り分けよう 辺で結ばれた異なる2頂点は色が異なるように 各頂点を塗る 2 1 1 2 3 4 4 2 2 2 3 1 1 4 3 4
グラフでモデル化して塗り分けよう もとの地図の領域を 対応する頂点の色で塗る 2 1 1 2 3 4 4 2 2 2 3 1 1 4 3 4
グラフでモデル化して塗り分けよう もとの地図の領域が塗り分けられる
四色定理（頂点塗り分けVer.） 平面グラフの頂点は 4色以下で塗り分けられる 2 1 1 2 3 4 4 2 2 2 3 1 1 4 3 4
六色定理（頂点塗り分けVer.） 平面グラフの頂点は ６色以下で塗り分けられる 2 5 1 2 3 4 4 2 6 2 3 1 1 4 3 5
五色定理（頂点塗り分けVer.） 平面グラフの頂点は ５色以下で塗り分けられる 2 5 1 2 3 4 4 2 2 2 3 1 1 4 3 5
五辺国補題 平面グラフには次数が5以下の頂点がある
五色定理（頂点塗り分けVer.）の証明 背理法Ver. 背理法で証明する 背理法の仮定 5色以下では塗り分けできない平面グラフがある 5色以下では塗り分けできない平面グラフのうち 頂点数が最小のものをひとつ選び G とおく 最小反例 G
五色定理（頂点塗り分けVer.）の証明 背理法Ver. 五辺国補題より、Gには次数が5以下の頂点がある 次数が5以下の頂点をひとつ選び v とおく v G 次数５以下
五色定理（頂点塗り分けVer.）の証明 背理法Ver. G-v は G より頂点数が少ない平面グラフ Gは最小反例だからG-vは5色以下で塗り分けられる G-ｖ を5色以下で塗り分ける G-v
五色定理（頂点塗り分けVer.）の証明 背理法Ver. vに塗れる色が余っているとき 余っている色でvを塗る 1 2 2 v 4 G 3 次数５以下
五色定理（頂点塗り分けVer.）の証明 背理法Ver. vに塗れる色が余っているとき 余っている色でvを塗る Gは5色以下で塗り分けられるのでGの定義に矛盾する 1 2 2 5 v 4 G 3 次数５以下
五色定理（頂点塗り分けVer.）の証明 背理法Ver. vに塗れる色が余っていないとき vのまわりに5色すべて登場している vの次数は５である 1 5 v1 2 v2 v5 v 4 G v4 v 3 3
五色定理（頂点塗り分けVer.）の証明 背理法Ver. v1から色１と色３の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 5 1 3 2 3 1 2 2 3 5 1 5 3 v1 2 v2 v5 v 4 G 1 3 1 4 1 4 v4 v 3 3 1 4 5 1
五色定理（頂点塗り分けVer.）の証明 背理法Ver. v1から色１と色３の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 5 1 3 2 3 1 2 2 3 5 1 5 3 v1 2 v2 v5 v 4 G 1 3 1 4 1 4 v4 v 3 3 1 4 5 1
五色定理（頂点塗り分けVer.）の証明 背理法Ver. v1から色１と色３の頂点だけを辿ってみる v3まで辿り着けないとき v1から辿れる範囲内の色１と色３を入れ替える 4 4 3 3 4 3 1 1 5 1 3 2 3 1 2 2 3 5 1 5 3 v1 2 v2 v5 v 4 G 1 3 1 4 1 4 v4 v 3 3 1 4 5 1
五色定理（頂点塗り分けVer.）の証明 背理法Ver. v1から色１と色３の頂点だけを辿ってみる v3まで辿り着けないとき v1から辿れる範囲内の色１と色３を入れ替える 4 4 3 1 4 3 1 3 5 1 1 2 1 3 2 2 3 5 3 5 1 v1 2 v2 v5 v 4 G 3 1 3 4 1 4 v4 v 3 3 3 4 5 3
五色定理（頂点塗り分けVer.）の証明 背理法Ver. v1から色１と色３の頂点だけを辿ってみる v3まで辿り着けないとき G-vは依然として塗り分けできている 4 4 3 1 4 3 1 3 5 1 1 2 1 3 2 2 3 5 3 5 1 v1 2 v2 v5 v 4 G 3 1 3 4 1 4 v4 v 3 3 3 4 5 3
五色定理（頂点塗り分けVer.）の証明 背理法Ver. v1から色１と色３の頂点だけを辿ってみる v3まで辿り着けないとき vの色を色１で塗るとGが塗り分けできてしまい矛盾 4 4 3 1 4 3 1 3 5 1 1 2 1 3 2 2 3 5 3 5 v5 1 v1 2 1 v2 v 4 G 3 1 3 4 1 4 v4 v 3 3 3 4 5 3
五色定理（頂点塗り分けVer.）の証明 背理法Ver. v1から色１と色３の頂点だけを辿ってみる v3まで辿り着けるとき v1から辿れる範囲内の色１と色３を入れ替えてもダメ 4 4 3 3 4 3 1 1 5 1 1 3 1 4 1 4 3 2 3 1 5 2 2 3 5 1 3 1 4 1 v1 5 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
五色定理（頂点塗り分けVer.）の証明 背理法Ver. v1から色１と色３の頂点だけを辿ってみる v3まで辿り着けるとき v2とv4が閉じた境界線で隔たれていることに注目 4 4 3 3 4 3 1 1 5 1 1 3 1 4 1 4 3 2 3 1 5 2 2 3 5 1 3 1 4 1 v1 5 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
五色定理（頂点塗り分けVer.）の証明 背理法Ver. v2から色2と色4の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 5 1 1 3 1 4 1 4 3 2 3 1 5 2 2 3 5 1 3 1 4 1 v1 5 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
五色定理（頂点塗り分けVer.）の証明 背理法Ver. v2から色2と色4の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 5 1 3 2 3 1 5 2 2 3 5 1 3 2 v 4 v4 2 4 3 2 2 4 v 3 3 2 4 v2 v5 1 4 1 v1 5 G 1 3 1 4 1 4 1 3 1 3 1
五色定理（頂点塗り分けVer.）の証明 背理法Ver. v2から色2と色4の頂点だけを辿ってみる v4までは辿り着けないので v2から辿れる範囲内の色2と色4を入れ替える 4 4 3 3 4 3 1 1 5 1 3 2 3 1 5 2 2 3 5 1 3 2 v 4 v4 2 4 3 2 2 4 v 3 3 2 4 v2 v5 1 4 1 v1 5 G 1 3 1 4 1 4 1 3 1 3 1
五色定理（頂点塗り分けVer.）の証明 背理法Ver. v2から色2と色4の頂点だけを辿ってみる v4までは辿り着けないので v2から辿れる範囲内の色2と色4を入れ替える 4 4 3 3 4 3 1 1 5 1 3 4 3 1 5 2 2 3 5 1 3 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 5 G 1 3 1 4 1 4 1 3 1 3 1
五色定理（頂点塗り分けVer.）の証明 背理法Ver. G-vは依然として塗り分けできている 4 4 3 3 4 3 1 1 5 1 3 4 3 1 5 2 2 3 5 1 3 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 5 G 1 3 1 4 1 4 1 3 1 3 1
五色定理（頂点塗り分けVer.）の証明 背理法Ver. G-vは依然として塗り分けできている vの色を色2で塗るとGが塗り分けできてしまい矛盾 以上より、五色定理は成り立つ 4 4 3 3 4 3 1 1 5 1 3 4 3 1 5 2 2 3 5 3 1 v5 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 2 1 2 1 v1 5 G 1 3 1 4 1 4 1 3 1 3 1
五色定理（頂点塗り分けVer.） 平面グラフの頂点は ５色以下で塗り分けられる 2 5 1 2 3 4 4 2 2 2 3 1 1 4 3 5
四色定理の ケンプの誤証明
The Four-Color Theorem 四色定理 平面上のどんな地図も ４色あれば塗り分けられる ※ 隣接する異なる領域は異なる色で塗る ※ 点のみで接する場合は隣接とはみなさない
四色問題の歴史（おさらい） 1852年 フランシス・ガスリー フレデリック・ガスリー ド・モルガン 18??年 ケイリー 1878年 ロンドン数学会 187９年 ケンプが証明した・・・？ 1890年 ヘイウッドが誤りを指摘 ケンプの証明方針を発展 1977年 アッペルとハーケンが証明
四色定理（頂点塗り分けVer.） 平面グラフの頂点は 4色以下で塗り分けられる 2 1 1 2 3 4 4 2 2 2 3 1 1 4 3 4
挑戦状 今から四色定理を証明します 証明の誤りを指摘してください
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 背理法で証明する 背理法の仮定 4色以下では塗り分けできない平面グラフがある 4色以下では塗り分けできない平面グラフのうち 頂点数が最小のものをひとつ選び G とおく 最小反例 G
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 五辺国補題より、Gには次数が5以下の頂点がある 次数が5以下の頂点をひとつ選び v とおく v G 次数５以下
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. G-v は G より頂点数が少ない平面グラフ Gは最小反例だからG-vは4色以下で塗り分けられる G-ｖ を4色以下で塗り分ける G-v
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. vに塗れる色が余っているとき 余っている色でvを塗る 1 2 2 v 1 G 3 次数５以下
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. vに塗れる色が余っているとき 余っている色でvを塗る Gは4色以下で塗り分けられるのでGの定義に矛盾する 1 2 2 4 v 1 G 3 次数５以下
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. vに塗れる色が余っていないとき vのまわりに4色すべて登場している vの次数は4または５である 1 2 2 v 4 G 3 次数４または５
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. vに塗れる色が余っていないとき 次の３つのケースが考えられる 1-2-3-4型 1-2-3-4-4型 1-2-3-4-2型 1 1 1 v1 2 v2 4 4 v4 v3 3 2 v2 v5 v v1 2 4 v 4 v3 3 2 v2 v5 v v1 v 4 v4 v3 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき 1 4 v1 2 v2 v5 v 4 G v4 v 3 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき v1から色１と色３の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 2 1 3 2 3 1 2 2 3 2 1 4 3 v1 2 v2 v5 v 4 G 1 3 1 4 1 4 v4 v 3 3 1 4 2 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき v1から色１と色３の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 2 1 3 2 3 1 2 2 3 2 1 4 3 v1 2 v2 v5 v 4 G 1 3 1 4 1 4 v4 v 3 3 1 4 2 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき v3まで辿り着けないとき v1から辿れる範囲内の色１と色３を入れ替える 4 4 3 3 4 3 1 1 2 1 3 2 3 1 2 2 3 2 1 4 3 v1 2 v2 v5 v 4 G 1 3 1 4 1 4 v4 v 3 3 1 4 2 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき v3まで辿り着けないとき v1から辿れる範囲内の色１と色３を入れ替える 4 4 3 1 4 3 1 3 2 1 1 2 1 3 2 2 3 2 3 4 1 v1 2 v2 v5 v 4 G 3 1 3 4 1 4 v4 v 3 3 3 4 2 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき v3まで辿り着けないとき G-vは依然として塗り分けできている 4 4 3 1 4 3 1 3 2 1 1 2 1 3 2 2 3 2 3 4 1 v1 2 v2 v5 v 4 G 3 1 3 4 1 4 v4 v 3 3 3 4 2 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき v3まで辿り着けないとき vの色を色１で塗るとGが塗り分けできてしまい矛盾 4 4 3 1 4 3 1 3 2 1 1 2 1 3 2 2 3 2 3 4 v5 1 v1 2 1 v2 v 4 G 3 1 3 4 1 4 v4 v 3 3 3 4 2 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき v3まで辿り着けるとき v1から辿れる範囲内の色１と色３を入れ替えてもダメ 4 4 3 3 4 3 1 1 2 1 1 3 1 4 1 4 3 2 3 1 2 2 2 3 2 1 3 1 4 1 v1 4 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき v3まで辿り着けるとき v2とv4が閉じた境界線で隔たれていることに注目 4 4 3 3 4 3 1 1 2 1 1 3 1 4 1 4 3 2 3 1 2 2 2 3 2 1 3 1 4 1 v1 4 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき v2から色2と色4の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 2 1 1 3 1 4 1 4 3 2 3 1 2 2 2 3 2 1 3 1 4 1 v1 4 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき v2から色2と色4の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 2 1 3 2 3 1 2 2 2 3 2 1 3 2 v 4 v4 2 4 3 2 2 4 v 3 3 2 4 v2 v5 1 4 1 v1 4 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき v4までは辿り着けないので v2から辿れる範囲内の色2と色4を入れ替える 4 4 3 3 4 3 1 1 2 1 3 2 3 1 2 2 2 3 2 1 3 2 v 4 v4 2 4 3 2 2 4 v 3 3 2 4 v2 v5 1 4 1 v1 4 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき v4までは辿り着けないので v2から辿れる範囲内の色2と色4を入れ替える 4 4 3 3 4 3 1 1 2 1 3 4 3 1 2 2 2 3 2 1 3 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 4 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき G-vは依然として塗り分けできている 4 4 3 3 4 3 1 1 2 1 3 4 3 1 2 2 2 3 2 1 3 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 4 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4型、1-2-3-4-4型のとき G-vは依然として塗り分けできている vの色を色2で塗るとGが塗り分けできてしまい矛盾 4 4 3 3 4 3 1 1 2 1 3 4 3 1 2 2 2 3 2 3 1 v5 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 2 1 2 1 v1 4 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき 1 2 v1 2 v2 v5 v 4 G v4 v 3 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v1から色１と色３の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 2 1 3 2 3 1 2 2 3 2 1 2 3 v1 2 v2 v5 v 4 G 1 3 1 4 1 4 v4 v 3 3 1 4 2 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v1から色１と色３の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 2 1 3 2 3 1 2 2 3 2 1 2 3 v1 2 v2 v5 v 4 G 1 3 1 4 1 4 v4 v 3 3 1 4 2 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v3まで辿り着けないとき v1から辿れる範囲内の色１と色３を入れ替える 4 4 3 3 4 3 1 1 2 1 3 2 3 1 2 2 3 2 1 2 3 v1 2 v2 v5 v 4 G 1 3 1 4 1 4 v4 v 3 3 1 4 2 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v3まで辿り着けないとき v1から辿れる範囲内の色１と色３を入れ替える 4 4 3 1 4 3 1 3 2 1 1 2 1 3 2 2 3 2 3 2 1 v1 2 v2 v5 v 4 G 3 1 3 4 1 4 v4 v 3 3 3 4 2 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v3まで辿り着けないとき G-vは依然として塗り分けできている 4 4 3 1 4 3 1 3 2 1 1 2 1 3 2 2 3 2 3 2 1 v1 2 v2 v5 v 4 G 3 1 3 4 1 4 v4 v 3 3 3 4 2 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v3まで辿り着けないとき vの色を色１で塗るとGが塗り分けできてしまい矛盾 4 4 3 1 4 3 1 3 2 1 1 2 1 3 2 2 3 2 3 2 v5 1 v1 2 1 v2 v 4 G 3 1 3 4 1 4 v4 v 3 3 3 4 2 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v3まで辿り着けるとき v1から辿れる範囲内の色１と色３を入れ替えてもダメ 4 4 3 3 4 3 1 1 2 1 1 3 1 4 1 4 3 2 3 1 2 2 2 3 2 1 3 1 4 1 v1 2 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v3まで辿り着けるとき v2とv4が閉じた境界線で隔たれていることに注目 4 4 3 3 4 3 1 1 2 1 1 3 1 4 1 4 3 2 3 1 2 2 2 3 2 1 3 1 4 1 v1 2 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v2から色2と色4の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 2 1 1 3 1 4 1 4 3 2 3 1 2 2 2 3 2 1 3 1 4 1 v1 2 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v2から色2と色4の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 2 1 3 2 3 1 2 2 2 3 2 1 3 2 v 4 v4 2 4 3 2 2 4 v 3 3 2 4 v2 v5 1 4 1 v1 2 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4までは辿り着けないので v2から辿れる範囲内の色2と色4を入れ替える 4 4 3 3 4 3 1 1 2 1 3 2 3 1 2 2 2 3 2 1 3 2 v 4 v4 2 4 3 2 2 4 v 3 3 2 4 v2 v5 1 4 1 v1 2 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4までは辿り着けないので v2から辿れる範囲内の色2と色4を入れ替える 4 4 3 3 4 3 1 1 2 1 3 4 3 1 2 2 2 3 2 1 3 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 2 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき G-vは依然として塗り分けできている 4 4 3 3 4 3 1 1 2 1 3 4 3 1 2 2 2 3 2 1 3 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 2 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき G-vは依然として塗り分けできている vの色を色2で塗ることができない！ 4 4 3 3 4 3 1 1 2 1 3 4 3 1 2 2 2 3 2 1 3 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 2 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v1から色１と色4の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 2 1 3 4 3 1 2 2 2 3 2 1 3 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 2 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v1から色１と色4の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 2 1 3 4 3 1 2 2 2 3 2 1 3 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 2 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4まで辿り着けないとき v1から辿れる範囲内の色１と色4を入れ替える 4 4 3 3 4 3 1 1 2 1 3 4 3 1 2 2 2 3 2 1 3 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 2 G 1 3 1 4 1 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4まで辿り着けないとき v1から辿れる範囲内の色１と色4を入れ替える 1 1 3 3 1 3 4 1 2 4 3 4 3 1 2 2 2 3 2 4 3 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 2 G 1 3 4 1 4 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4まで辿り着けないとき G-vは依然として塗り分けできている・・・本当に？？ 1 1 3 3 1 3 4 1 2 4 3 4 3 1 2 2 2 3 2 4 3 4 v 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 2 G 1 3 4 1 4 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4まで辿り着けないとき G-vは依然として塗り分けできている・・・本当に？？ 1 1 3 3 1 3 4 1 2 4 3 4 3 1 2 2 2 3 v1とv2が辺で 結ばれてるかも 2 4 3 4 v v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 2 4 G 1 3 4 1 4 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4まで辿り着けないとき G-vは依然として塗り分けできている・・・本当に？？ 1 3 1 3 4 （3）1414のくだり 2 1 3 4 1 3 3 4 3 1 2 2 2 3 2 4 2424のくだりは 2 後回しにしよう 3 v2 v4 2 3 3 4 4 2 v 3 4 4 2 （2）2424のくだり 4 v 1 2 1 v1 v5 4 G 1 （１）1313のくだり 4 1 4 4 1 3 1 3 1
途中まで戻ってやりなおし
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v3まで辿り着けるとき v2とv4は閉じた境界線で隔たれている 4 4 3 3 4 3 1 1 2 1 1 3 1 4 1 4 3 2 3 1 2 2 2 3 2 1 3 1 4 1 v1 2 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v1から色１と色4の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 2 1 1 3 1 4 1 4 3 2 3 1 2 2 2 3 2 1 3 1 4 1 v1 2 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v1から色１と色4の頂点だけを辿ってみる 4 4 3 3 4 3 1 1 2 1 1 3 1 4 1 4 3 2 3 1 2 2 2 3 2 1 3 1 4 1 v1 2 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4まで辿り着けないとき v1から辿れる範囲内の色１と色4を入れ替える 4 4 3 3 4 3 1 1 2 1 1 3 1 4 1 4 3 2 3 1 2 2 2 3 2 1 3 1 4 1 v1 2 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4まで辿り着けないとき v1から辿れる範囲内の色１と色4を入れ替える 1 1 3 3 1 3 4 1 2 4 1 3 4 1 4 4 3 2 3 1 2 2 2 3 2 4 3 1 4 1 v1 2 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4まで辿り着けないとき G-vは依然として塗り分けできている 1 1 3 3 1 3 4 1 2 4 1 3 4 1 4 4 3 2 3 1 2 2 2 3 2 4 3 1 4 1 v1 2 3 2 v2 v5 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4まで辿り着けないとき vの色を色１で塗るとGが塗り分けできてしまい矛盾 1 1 3 3 1 3 4 1 2 4 1 3 4 1 4 4 3 2 3 1 2 2 2 3 2 4 3 4 1 v1 2 v5 1 3 2 v2 1 1 v 4 G v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4まで辿り着けるとき v1から辿れる範囲内の色１と色4を入れ替えてもダメ 4 1 4 3 3 4 3 1 1 2 1 1 3 2 3 1 2 2 2 2 3 1 1 3 4 1 3 2 v2 v5 4 1 v1 2 1 v 1 G 1 3 1 4 4 4 4 1 4 v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4まで辿り着けるとき v5とv3は閉じた境界線で隔たれている 4 1 4 3 3 4 3 1 1 2 1 1 3 2 3 1 2 2 2 2 3 1 1 3 4 1 3 2 v2 v5 4 1 v1 2 1 v 1 G 1 3 1 4 4 4 4 1 4 v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v2から色2と色4の頂点だけを辿ってみる 4 1 4 3 3 4 3 1 1 2 1 1 3 2 3 1 2 2 2 2 3 1 1 3 4 1 3 2 v2 v5 4 1 v1 2 1 v 1 G 1 3 1 4 4 4 4 1 4 v4 v 3 3 1 3 1 3
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v2から色2と色4の頂点だけを辿ってみる 4 1 4 3 3 4 3 1 1 2 1 1 2 3 2 3 1 1 3 1 2 2 4 v 1 1 4 v4 2 4 3 2 2 4 v 3 3 2 4 v2 v5 1 4 1 v1 2 G 3 2 2 4 1 3 1 4 4 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4までは辿り着けないので v2から辿れる範囲内の色2と色4を入れ替える 4 1 4 3 3 4 3 1 1 2 1 1 2 3 2 3 1 1 3 1 2 2 4 v 1 1 4 v4 2 4 3 2 2 4 v 3 3 2 4 v2 v5 1 4 1 v1 2 G 3 2 2 4 1 3 1 4 4 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v4までは辿り着けないので v2から辿れる範囲内の色2と色4を入れ替える 4 1 4 3 3 4 3 1 1 2 1 1 2 3 4 3 1 1 3 1 2 4 4 v 1 1 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 2 G 3 2 2 4 1 3 1 4 4 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v5から色2と色３の頂点だけを辿ってみる 4 1 4 3 3 4 3 1 1 2 1 1 2 3 4 3 1 1 3 1 2 4 4 v 1 1 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 v5 1 2 1 v1 2 G 3 2 2 4 1 3 1 4 4 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v5から色2と色３の頂点だけを辿ってみる 4 1 4 3 3 4 3 1 1 2 1 2 1 2 3 1 2 2 3 4 1 3 1 2 4 v 1 1 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 1 2 1 v1 v5 2 G 4 3 2 3 4 3 2 2 3 1 3 1 4 4 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v3までは辿り着けないので v5から辿れる範囲内の色2と色３を入れ替える 4 1 4 3 3 4 3 1 1 2 1 2 1 2 3 1 2 2 3 4 1 3 1 2 4 v 1 1 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 1 2 1 v1 v5 2 G 4 3 2 3 4 3 2 2 3 1 3 1 4 4 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき v3までは辿り着けないので v5から辿れる範囲内の色2と色３を入れ替える 4 1 4 2 3 4 3 1 1 2 1 3 1 3 2 1 3 3 2 4 1 3 1 2 4 v 1 1 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 1 2 1 v1 v5 3 G 4 3 3 2 4 3 3 2 2 1 3 1 4 4 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき G-vは依然として塗り分けできている 4 1 4 2 3 4 3 1 1 2 1 3 1 3 2 1 3 3 2 4 1 3 1 2 4 v 1 1 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 1 2 1 v1 v5 3 G 4 3 3 2 4 3 3 2 2 1 3 1 4 4 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 1-2-3-4-2型のとき G-vは依然として塗り分けできている vの色を色2で塗るとGが塗り分けできてしまい矛盾 4 1 4 2 3 4 3 1 1 2 1 3 1 3 2 1 3 3 2 4 3 1 v5 1 2 4 1 1 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 2 1 2 1 v1 v 3 G 4 3 3 2 4 3 3 2 2 1 3 1 4 4 4 1 3 1 3 1
四色定理（頂点塗り分けVer.）の証明？ 背理法Ver. 以上より、四色定理は成り立つ 4 1 4 2 3 4 3 1 1 2 1 3 1 3 2 1 3 3 2 4 3 1 v5 1 2 4 1 1 4 v4 4 2 3 4 4 2 v 3 3 4 2 v2 2 1 2 1 v1 v 3 G 4 3 3 2 4 3 3 2 2 1 3 1 4 4 4 1 3 1 3 1
証明の誤りを指摘してください
証明の誤り v1からv3への閉じた境界線と v1からv4への閉じた境界線が v1とv以外で交差するケースを見逃している！ 1 4 4 1 1 2 3 v1 1 2 v2 v5 4 1 3 3 v v4 4 3 v3 1 1 1 3 4 1 G 4 4 1 3 3 1
証明の誤り 下図のケースを考えてみよう 1 4 4 1 1 2 3 v1 1 2 v2 v5 4 1 3 3 v v4 4 3 v3 1 1 1 3 4 1 G 4 4 1 3 3 1
証明の誤り v2から色2と色4の頂点だけを辿ってみる v4までは辿り着けないので v2から辿れる範囲内の色2と色4を入れ替える 1 4 4 1 1 2 3 v1 1 2 v2 v5 4 1 3 4 3 v v4 4 3 v3 1 1 2 1 3 4 1 G 4 4 1 3 3 1
証明の誤り v2から色2と色4の頂点だけを辿ってみる v4まで辿り着けないので v2から辿れる範囲内の色2と色4を入れ替える 1 4 4 1 1 2 3 v1 1 4 v2 v5 4 1 3 2 3 v v4 4 3 v3 1 1 4 1 3 4 1 G 4 2 1 3 3 1
証明の誤り v5から色2と色３の頂点だけを辿ってみる 1 4 4 1 1 2 3 3 v1 1 4 v2 v5 4 1 3 2 3 v v4 4 3 v3 1 1 2 1 3 4 1 G 4 4 2 1 3 3 1
証明の誤り v5から色2と色３の頂点だけを辿ってみる v3まで辿り着け・・・てしまう！！！？？！？ v5から辿れる範囲内の色2と色３を入れ替えてもダメ 1 4 4 1 1 2 3 3 v1 1 4 v2 v5 4 1 3 2 3 v v4 4 3 v3 1 1 2 1 3 4 1 G 4 4 2 1 3 3 1
四色問題の歴史（おさらい） 1852年 フランシス・ガスリー フレデリック・ガスリー ド・モルガン 18??年 ケイリー 1878年 ロンドン数学会 187９年 ケンプが証明した・・・？ 1890年 ヘイウッドが誤りを指摘 ケンプの証明方針を発展 1977年 アッペルとハーケンが証明